So given a set of points n there is a Voronoi-diagram given which was created in $\mathcal{O}(n)$. Now is it possible to find the closest pair of points of this set in $\mathcal{O}(n)$?
I know that the closest pair of points in the set of points corresponds to 2 adjacent cells in the Voronoi-diagram, but checking every 2 adjacent cells would be slower than $\mathcal{O}(n)$ so there might be a better way? I am also aware of the relationship between a Voronoi-diagram and the Delauny-triangulation but I cant't find any hint in this direction either.
Any hint is appreciated!
We only need to consider pairs of points whose Voronoi cells are adjacent, i.e. we can check pairs of points that determine the boundaries of each of the Voronoi cells. Since the Voronoi diagram is planar, there are only $O(n)$ boundary components to check.