Two-Dimensional Voronoi Diagrams in the L p -Metric
D. T. Lee · Journal of the ACM · 1980
The Voronoi diagram, also known as the Thiessen diagram, for a set of N points in the Cartesian plane in which the L,-metnc is the distance measure, where p is a real number between 1 and 0o inclusive, is defined, and an algorithm for constructing the dmgram m O(NlogN) tune is presented This algonthm uses the divide-and-conquer technique.Many proximity problems revolving a set of points, such as finding the nearest neighbor of a given point, finding the minimum spamung tree, findmg the smallest circle (m the Lp-metric) enclosing the point set, etc., can be solved very efficiently via the diagram The running time of the algorithm presented is also shown to be optimal to within a constant factor.