Logo image
Back
An optimal algorithm for constructing oriented voronoi diagrams and geographic neighborhood graphs
Journal article   Peer reviewed

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

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

Abstract

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

Metrics

1 Record Views

Details

Logo image