Список процессов треугольников Делоне в алгоритме Вороного

Question

Учитывая список треугольников Делоне, необходимо получить список ребер, которые будут частью тесселяции Вороного.

псевдокод скелета программы является:

getVoronoi(list<point> points) { 
    list<triangle> triangles = delaunayTriangulation(points); 
    list<edge> edges = voronoiTessellation(triangles); 

    //Do something with "edges". 
} 

Пусть N быть размером points, зная, что Триангуляция Делоне (точки) является O(N log N) и triangles=<T1,T2,...TM>, а затем, в voronoiTessellation(triangles) сложность должна быть меньше или равна O(N log N).

Способ расчета тесселяции:

voronoiTessellation (list<Triangle> triangles) { 
    list<Edge> edges; 
    map<Triangle, Point> centers; 

    foreach(Triangle triangle in triangles) { 
     centers.add(triangle,triangle.calculateCircumcircle()); 
    } 

    foreach(<Triangle triangle,Point point> in points) { 
     list<edges> triangleEdges = triangle.getEdges(); 
     foreach (Edge edge in triangleEdges) { 
      Triangle neighbor = searchNeighbor(edge); 
      Point neighborCircumcenter = centers.get(neighbor); 
      Line line(point, neighborCircumcenter); 
      //todo only add this edge once 
      edges.add(line); 
     } 
    } 

    return edges; 
} 

Мой вопрос: какова сложность voronoiTessellation(T)? Он меньше или равен O(N log N)?

Спасибо!

Answer 1

Этот алгоритм является O (N), если вы можете выполнять поискNeighbor (edge) и center.get() в постоянное время или O (N log N), если searchNeighbor (edge) занимает время O (log N).

Либо одно из них должно быть легко встретить, сделав карту: край -> (треугольник, треугольник), с которым будет выполняться поискNeighbor().

Если вы используете хэш-карты, вы получите ожидаемое время O (N). Есть O (N) треугольников в триангуляции Делоне из N точек, так:

• Строительные центры добавляет O (N) центров и занимает O (N) времени

• Есть O (N) треугольник, точечные пары

• Есть 3 ребра в треугольнике

• добавление O (N) ребер к результату, в O (N) время