How to compute convex hull of set points from Voronoi diagram in linear time
Given $n$ points in the plane and their Voronoi diagram, how do I prove that the convex hull of the points can be computed in linear time?
$\endgroup$2 Answers
$\begingroup$Having a Voronoi diagram, we can calculate the Delaunay triangulation in linear time. It is also obvious that the boundary of the Delaunay triangulation is the convex hull. So it is enough to find the cells which are neighbors of the infinity vertex $V_\infty$. Since the cells are stored in a double-linked list the search operations take constant time.
$\endgroup$ 1 $\begingroup$One of the properties of Voronoi diagrams is
A cell (or face) of the Voronoi diagram is unbounded if and only if the corresponding site lies on the convex hull.
If you are given the Voronoi diagram, you can iterate, in $\mathcal{O}(n)$ time, its faces (or cells) and check which ones are unbounded. Therefore, you can get the set that forms the convex hull in $\mathcal{O}(n)$ by taking the sites of the infinite faces.
$\endgroup$ 0
