A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations

Gary L. Miller, Donald R. Sheehy

We describe a new algorithm for computing the Voronoi diagram of a set of $n$ points in constant-dimensional Euclidean space. The running time of our algorithm is $O(f \log n \log…