An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

1 November 1987

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-36 (11) , 1349-1354
https://doi.org/10.1109/tc.1987.5009474

Abstract

The kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E² subdivides E² into maximal regions such that all points within a given region have the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in O(n² log n + k(n - k) log² n) time, O(k(n - k)) storage, and in O(n² + k(n - k) log² n) time, O(n²) storage, respectively.

Keywords

This publication has 14 references indexed in Scilit:

Sequencing-by-hybridization revisited: the analog-spectrum proposal
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
On k-Hulls and Related Problems
SIAM Journal on Computing, 1987
Constructing Arrangements of Lines and Hyperplanes with Applications
SIAM Journal on Computing, 1986
A sweepline algorithm for Voronoi diagrams
Published by Association for Computing Machinery (ACM) ,1986
The power of geometric duality
BIT Numerical Mathematics, 1985
On k-Nearest Neighbor Voronoi Diagrams in the Plane
IEEE Transactions on Computers, 1982
Maintenance of configurations in the plane
Journal of Computer and System Sciences, 1981
Voronoi diagrams from convex hulls
Information Processing Letters, 1979
Closest-point problems
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1975
Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen.
Journal für die reine und angewandte Mathematik (Crelles Journal), 1850