A STRAIGHTFORWARD ITERATIVE ALGORITHM FOR THE PLANAR VORONOI DIAGRAM

被引：12

作者：

TIPPER, JC

机构：

[1] Department of Geology, Australian National University, A.C.T., 2601, G.P.O. Box 4, Canberra

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 34卷 / 03期

关键词：

Applications: graphics; spatial data structures; triangulation; Voronoi diagram;

D O I：

10.1016/0020-0190(90)90095-F

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Several published algorithms construct the planar N-point Voronoi diagram by adding the points in turn to a diagram already constructed for a subset of those points. The algorithm described here works in this way, but stipulates that every added point be outside the convex hull of the already constructed partial diagram. This stipulation, which is implemented by presorting the points by increasing x-coordinate, ensures that the core of the algorithm runs in almost linear time. The algorithm is inherently iterative, not recursive, and provides a rapid, efficient way to construct the Voronoi diagram for large data sets. © 1990.

引用

页码：155 / 160

页数：6

共 50 条

[31] An Improved K-means Clustering Algorithm Based on the Voronoi Diagram Method [J].

Huo, Jiuyuan ;

Zhang, Honglei .

ADVANCES IN SWARM INTELLIGENCE, ICSI 2016, PT II, 2016, 9713 :107-114

[32] A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters [J].

Cheilaris, Panagiotis ;

Khramtcova, Elena ;

Langerman, Stefan ;

Papadopoulou, Evanthia .

ALGORITHMICA, 2016, 76 (04) :935-960

[33] Preliminary Study on A Lightning Location Algorithm with Voronoi Diagram as the Constraint for Nonlinear Optimization [J].

Wang Yu ;

Gu Shanqiang ;

Meng Gang ;

Li Jian ;

Feng Zhiqiang ;

Li Chang .

2021 35TH INTERNATIONAL CONFERENCE ON LIGHTNING PROTECTION (ICLP) AND XVI INTERNATIONAL SYMPOSIUM ON LIGHTNING PROTECTION (SIPDA), 2021,

[34] A Clustering Density Weighted Algorithm of KNN Fingerprint Location Based on Voronoi Diagram [J].

Dang, Xiaochao ;

Hei, Yili ;

Hao, Zhanjun .

WIRELESS SENSOR NETWORKS (CWSN 2017), 2018, 812 :175-190

[35] AN OPTIMAL PARALLEL ALGORITHM USING EXCLUSIVE READ WRITES FOR THE RECTILINEAR VORONOI DIAGRAM [J].

GUHA, S .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1993, 3 (01) :37-52

[36] Electric Vehicle Charging Station Planning Based on Immune Algorithm and Voronoi Diagram [J].

Li, Yongjing ;

Pei, Wenhui ;

Xu, Di .

2021 PROCEEDINGS OF THE 40TH CHINESE CONTROL CONFERENCE (CCC), 2021, :1532-1537

[37] The graph Voronoi diagram with applications [J].

Erwig, M .

NETWORKS, 2000, 36 (03) :156-163

[38] PRF: A Fast Parallel Relaxed Flooding Algorithm for Voronoi Diagram Generation on GPU [J].

Wang, Jue ;

Ino, Fumihiko ;

Ke, Jing .

2023 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM, IPDPS, 2023, :713-723

[39] A Raster Voronoi Diagram Generating Algorithm Using Edge Attribution and Bilateral Scanning [J].

Wang, Lei ;

Song, Zhixue ;

Yin, Nan ;

Cheng, Gang .

Wuhan Daxue Xuebao (Xinxi Kexue Ban)/Geomatics and Information Science of Wuhan University, 2024, 49 (12) :2323-2328

[40] A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters [J].

Panagiotis Cheilaris ;

Elena Khramtcova ;

Stefan Langerman ;

Evanthia Papadopoulou .

Algorithmica, 2016, 76 :935-960

← 1 2 3 4 5 →