Voronoi算法中Delaunay三角形的处理列表

Question

给定Delaunay三角形的列表，有必要获得将成为Voronoi镶嵌的一部分的边的列表。

程序骨架的伪代码是：

getVoronoi(list<point> points) {
    list<triangle> triangles = delaunayTriangulation(points);
    list<edge> edges = voronoiTessellation(triangles);
    //Do something with "edges".
}

设N为points的大小，已知delaunayTriangulation（点）为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

如果您可以在恒定时间内执行searchNeighbor（edge）和centers.get（），则此算法为O（N）；如果searchNeigh（edge。

其中任何一个都应该很容易通过制作地图来满足：首先是edge->（三角形，三角形），searchNeighbor（）会参考它。

如果你使用散列映射，你会得到预期的O（N）时间。在N点的Delaunay三角测量中有O（N）个三角形，因此：

• 建筑中心增加O（N）个中心，并占用O（N）时间

• 有O（N）三角形，点对

• 每个三角形有3条边

• 在O（N）时间中，向结果添加O（N