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
相关论文
共 14 条
12