A New Approach to Output-Sensitive Voronoi Diagrams and

We present an algorithm for computing Voronoi di-agrams and Delaunay triangulations of point sets in Rd. We also give an output-sensitive analysis, prov-ing that the running time is at most O(m log n log ∆), where n is the input size, m is the output size, and the spread ∆ is the ratio of the diameter to the closest pair distance. For many realistic settings, the spread is polynomial in n, in which case we have the only known algorithm that is within a poly-logarithmic factor of optimal for the entire range of output sizes and any fixed dimension.