How to extract the convex hull of a set of points from their Voronoi diagram

I need an algorithm for calculating the convex hull of a set of points from the Voronoi Diagram of the points in O(n). The Voronoi diagram is contained in a bounding box and is stored as a doubly connected edge list. The input is a half edge whose origin is on the bounding box.

I know that two poi开发者_开发百科nts are adjacent on the convex hull iff they share an infinitely long voronoi edge.

If you have a bounding box large enough so that only infinite cells have bounding edges, the task doesn't seem tough. Iterate through the bounding edges, for each of them, traverse it forward and backward to find first non-bounding edges F and B. Mark current and all bounding edges found during traverse as used. Edges F and B would be infinite if the box won't exist. Thus, they touch faces (fF and fB) who's 'centers' are part of the convex hull (current face is C), and cross-edge C-to-F is the part of a convex hull. Take face fF and iterate from the F's twin forward to find next non-bounding edge, say, F1. If it's equal to 'B'-twin (or it's bounding edges were used), we are finished. If not, traverse the next neighbour ('fF1').

I believe it's possible to compute the convex hull of Voronoi Diagram in O(n) time.

In case of a given Voronoi diagram and a vertex that shall reside in the CH, you may able to iterate through the Voronoi Diagram's cells and expend the convex hull just like been done in Grahm scan algorithm but with different manner.

There is only one theory missing here, watch next...

According to Computational Geometry by Springer the M4 book, Theorem 7.4: A point q is a vertex of Vor(P) if and only if its largest empty circle C_p(q) contains three or more sites on it's boundary. Which means that the sites that need to be check every iteration is a done in O(1), which mean that you only have to iterate through O(n) sites.

According the theorem 7.3, the number of vertices in the Voronoi diagram of a ste of n points sites in a plain it at most 2n-5 (linear order).

Therefor it's possible to compute the CH of Voronoi diagram in O(n) time.