Given a Voronoi diagram created in $\mathcal{O}(n)$, is it possible to find the closest pair of points in $\mathcal{O}(n)$? 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!
 A: 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.
A: This is only possible if the size of the Voronoi diagram is actually ${\mathcal O}(n)$. In dimension $>2$, the total number of pairs of neighboring cells may be larger than ${\mathcal O}(n)$. In three dimensions, the Delaunay tetradedralization may contain ${\mathcal O}(n^2)$ tetrahedra (and edges), as shown in the example in this image from Attali, D.; Boissonnat, J.-D., A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces, Discrete Comput. Geom. 31, No. 3, 369-384 (2004).
Vertices are neighbors in the Voronoi diagram if they contain correspond to an edge in the Delaunay triangulation. So in this case, would need to iterator over ${\mathcal O}(n^2)$ pairs to find the closest pair of points. In those cases, the Voronoi diagram has a size of ${\mathcal O}(n^2)$ and thus will be difficult to use for anything in ${\mathcal O}(n)$ time.
