AN OPTIMAL ALGORITHM FOR CONSTRUCTING ORIENTED VORONOI DIAGRAMS AND GEOGRAPHIC NEIGHBORHOOD GRAPHS

被引：11
|
作者：
CHANG, MS [1 ]
HUANG, NF [1 ]
TANG, CY [1 ]
机构：
[1] NATL TSING HUA UNIV,INST COMP SCI,HSINCHU 30043,TAIWAN
来源：
INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 05期
关键词：
Computational geometry; geographic neighborhood graph; oriented Voronoi diagram;
D O I：
10.1016/0020-0190(90)90054-2
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Given n points on the plane, we propose an O(n log n) algorithm to construct the oriented Voronoi diagram and the geopraphic neighborhood graph of these n points. We also show that both problems have the same lower bound of Ω(n log n) and hence the proposed algorithm is optimal. © 1990.
引用
收藏
页码：255 / 260
页数：6
相关论文
共 16 条
  • [1] Constructing voronoi diagrams in the L1 metric using the geographic nearest neighbors
    Wee, Y
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2001, E84A (07) : 1755 - 1760
  • [2] A parallel algorithm for constructing Voronoi diagrams based on point-set adaptive grouping
    Wang, Jiechen
    Cui, Can
    Rui, Yikang
    Cheng, Liang
    Pu, Yingxia
    Wu, Wenzhou
    Yuan, Zhenyu
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2014, 26 (02): : 434 - 446
  • [3] A Faster Algorithm of Higher Order Voronoi Diagrams
    Hu, Lixia
    Liu, Hongjuan
    Xu, Baiquan
    2015 SEVENTH INTERNATIONAL CONFERENCE ON MEASURING TECHNOLOGY AND MECHATRONICS AUTOMATION (ICMTMA 2015), 2015, : 6 - 9
  • [4] Algorithm for creating Voronoi diagrams for two-dimensional riemannian manifolds
    Cheng, Dan
    Yang, Qin
    Li, Ji-Gang
    Cai, Qiang
    Ruan Jian Xue Bao/Journal of Software, 2009, 20 (09): : 2407 - 2416
  • [5] An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
    Cecilia Bohler
    Rolf Klein
    Chih-Hung Liu
    Algorithmica, 2019, 81 : 2317 - 2345
  • [6] An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams
    Bohler, Cecilia
    Klein, Rolf
    Liu, Chih-Hung
    ALGORITHMICA, 2019, 81 (06) : 2317 - 2345
  • [7] ON CONSTRUCTING THE RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN K-DIMENSIONAL SPACES
    SU, TH
    CHANG, RC
    COMPUTING, 1991, 46 (02) : 121 - 130
  • [8] A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
    Bohler, Cecilia
    Liu, Chih-Hung
    Papadopoulou, Evanthia
    Zavershynskyi, Maksym
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8889 : 27 - 37
  • [9] A DIVIDE-AND-CONQUER ALGORITHM FOR CONSTRUCTING RELATIVE NEIGHBORHOOD GRAPH
    HUANG, NF
    BIT, 1990, 30 (02): : 196 - 206
  • [10] A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
    Berman, P
    Lingas, A
    THEORETICAL COMPUTER SCIENCE, 1997, 174 (1-2) : 193 - 202
12