IEICE Trans - Constructing Voronoi Diagrams in the <I>L</I><SUB>1</SUB> Metric Using the Geographic Nearest Neighbors

Constructing Voronoi Diagrams in the L₁ Metric Using the Geographic Nearest Neighbors

Youngcheul WEE

Publication
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:
DOI:
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword:
computational geometry,  Voronoi diagram,  parallel algorithm,  L₁ metric,

Full Text: PDF>>

Summary:
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 L₁ metric. In general, there is no inclusion relationship between the Delaunay triangulation and the octant neighbor graph. We however find that under the L₁ 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 L₁ metric. This algorithm takes O(n log n) sequential time for constructing the Delaunay triangulation in the L₁ metric. This algorithm can easily be parallelized, and takes O(log n) time with O(n) processors on a CREW-PRAM.