Logo image
返回
An optimal algorithm for constructing oriented voronoi diagrams and geographic neighborhood graphs
期刊文章   同儕審查

An optimal algorithm for constructing oriented voronoi diagrams and geographic neighborhood graphs

Maw Shang Chang, Nen-Fu Huang 和 Chuan-Yi Tang
Information Processing Letters, 卷.35(5), 頁碼.255-260
08/1990
DOI: https://doi.org/10.1016/0020-0190(90)90054-2

摘要

Computational geometry geographic neighborhood graph oriented Voronoi diagram Computational Theory and Mathematics
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.

相關連結

指標

1 檢視次數

詳細資料

Logo image