Expected 0(N) and 0(N4/3) Algorithms for Constructing Voronoi Diagrams in Two and Three Dimensions
Bentley, Weide and Yao have proposed an expected 0(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 0(N ) and 0(N4/3) algorithms for constructing Voronoi diagrams in two and three dimensions, respectively. Computational experience is presented for the algorithm in two dimensions.
Expected 0(N) and 0(N4/3) Algorithms for Constructing Voronoi Diagrams in Two and Three Dimensions, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NBS.IR.87-3679
(Accessed December 11, 2023)