The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kertas kerja ini memperkenalkan pendekatan baharu berdasarkan jiran terdekat geografi untuk membina triangulasi Delaunay (dua rajah Voronoi) bagi satu set n tapak dalam pesawat di bawah L1 metrik. Secara umum, tiada hubungan kemasukan antara triangulasi Delaunay dan graf jiran oktan. Kami bagaimanapun mendapati bahawa di bawah L1 metrik graf jiran oktant mengandungi sekurang-kurangnya satu tepi setiap segi tiga dalam triangulasi Delaunay. Dengan menggunakan pemerhatian ini dan menggunakan skema pokok julat, kami mereka bentuk algoritma untuk membina triangulasi Delaunay (dengan itu gambar rajah Voronoi) dalam L1 metrik. Algoritma ini mengambil O(n log n) masa berurutan untuk membina triangulasi Delaunay dalam L1 metrik. Algoritma ini dengan mudah boleh disejajarkan, dan mengambil O(log n) masa dengan O(n) pemproses pada CREW-PRAM.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Youngcheul WEE, "Constructing Voronoi Diagrams in the L1 Metric Using the Geographic Nearest Neighbors" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 7, pp. 1755-1760, July 2001, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_7_1755/_p
Salinan
@ARTICLE{e84-a_7_1755,
author={Youngcheul WEE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constructing Voronoi Diagrams in the L1 Metric Using the Geographic Nearest Neighbors},
year={2001},
volume={E84-A},
number={7},
pages={1755-1760},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={July},}
Salinan
TY - JOUR
TI - Constructing Voronoi Diagrams in the L1 Metric Using the Geographic Nearest Neighbors
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1755
EP - 1760
AU - Youngcheul WEE
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2001
AB - 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.
ER -