Expected O(N) and O(N sup 4/3) Algorithms for Constructing Voronoi Diagrams in Two and Three Dimensions

摘要

Bentley, Weide and Yao have proposed an expected O(N) cell technique for computing Voronoi diagrams in two dimensions that does not generalize readily to three. In this paper their work is further developed and generalized to produce expected O(N) and O(N sup 4/3) algorithms for constructing Voronoi diagrams in two and three dimensions, respectively. Computational experience is presented for the algorithm in two dimensions.