Constructing voronoi diagrams in the L1 metric using the geographic nearest neighbors

This paper introduces a new approach based on the geographic nearest neighbors for constructing the Delaunay triangulation (a dual of the Voronoi diagram) of a aet of n sites in the plane under the L-1 metric. In general, there is no inclusion relationship between the Delaunay triangulation and the octant neighbor graph. We however find that under the L1 metric the octant neighbor graph contains at least one edge of each triangle in the Delaunay triangulation. By using this observation and employing a range tree scheme, we design an algorithm for constructing the Delaunay triangulation (thus the Voronoi diagram) in the L1 metric. This algorithm takes O(n log n) sequential time for constructing the Delaunay triangulation in the L1 metric. This algorithm can easily be parallelized, and takes O(log n) time with O(n) processors on a CREW-PRAM.