Constructing Voronoi Diagrams in the L_1 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 set 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 L_1 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_1 metric. This algorithm takes O(n log n) sequential time for constructing the Delaunay triangulation in the L_1 metric. This algorithm can easily be parallelized, and takes O(log n) time with O(n) processors on a CREW-PRAM.

• 2001-07-01

著者

• Wee Youngcheul

  Faculty Members Of Ajou University

関連論文

• Constructing Voronoi Diagrams in the L_1 Metric Using the Geographic Nearest Neighbors

スポンサーリンク