Process list of Delaunay triangles in Voronoi algorithm

Question

Given a list of Delaunay triangles, it is necessary to obtain a list of the edges that will be part of the Voronoi tessellation.

A pseudocode of the skeleton of the program is:

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

    //Do something with "edges".
}

Let N be the size of points, knowing that delaunayTriangulation(points) is O(N log N) and triangles=<T1,T2,...TM>, then, in voronoiTessellation(triangles) the complexity must be less or equal than O(N log N).

A way to calculate the tessellation is:

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;
}

My question is: what is the complexity of voronoiTessellation(T)? It is less or equal than O(N log N)?

Thanks!

Answer 1

This algorithm is O(N) if you can do searchNeighbor(edge) and centers.get() in constant time, or O(N log N) if searchNeighbor(edge) takes O(log N) time.

Either one of those should be easy to meet by making a map: edge -> (triangle,triangle) first, which searchNeighbor() would consult.

If you use hash maps, you'll get expected O(N) time. There are O(N) triangles in the Delaunay triangulation of N points, so:

• Building centers adds O(N) centers and takes O(N) time

• There are O(N) Triangle,point pairs

• There are 3 edges per triangle

• You add O(N) edges to the result, in O(N) time