Constructing Voronoi Diagrams in the L1 Metric Using the Geographic Nearest Neighbors

Youngcheul WEE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.7   pp.1755-1760
Publication Date: 2001/07/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
computational geometry,  Voronoi diagram,  parallel algorithm,  L1 metric,  

Full Text: PDF>>
Buy this Article

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 set of n sites in the plane under the L1 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.