Given a DCEL, how do I find the closest pair of sites?

Question

Given a DCEL, how do I find the closest pair of sites?

Say the given DCEL is for a Voronoi diagram, how do I find the closest pair of sites? And what is the time complexity?

Answer 1

The simplest way to do it is to iterate over all edges, find their adjoining faces, compute the distance between the Voronoi centers, and return the smallest pair. If your DCEL implementation is such that you cannot iterate directly over edges, you can use any graph-traversal algorithm (depth-first, breadth-first, etc.) to do the iteration.

In any case, the time complexity is proportional to the size of your input datastructure.