An improved algorithm for constructing kth-order Voronoi diagrams
Chazelle B, Edelsbrunner H. 1987. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Transactions on Computers. 36(11), 1349–1354.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
Abstract
he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E2 subdivides E2 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(n2 log n + k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time, O(n2) storage, respectively.
Publishing Year
Date Published
1987-11-01
Journal Title
IEEE Transactions on Computers
Publisher
IEEE
Acknowledgement
We would like to thank two anonymous referees for their constructive criticism.
Volume
36
Issue
11
Page
1349 - 1354
ISSN
eISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Transactions on Computers. 1987;36(11):1349-1354. doi:10.1109/TC.1987.5009474
Chazelle, B., & Edelsbrunner, H. (1987). An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Transactions on Computers. IEEE. https://doi.org/10.1109/TC.1987.5009474
Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing Kth-Order Voronoi Diagrams.” IEEE Transactions on Computers. IEEE, 1987. https://doi.org/10.1109/TC.1987.5009474.
B. Chazelle and H. Edelsbrunner, “An improved algorithm for constructing kth-order Voronoi diagrams,” IEEE Transactions on Computers, vol. 36, no. 11. IEEE, pp. 1349–1354, 1987.
Chazelle B, Edelsbrunner H. 1987. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Transactions on Computers. 36(11), 1349–1354.
Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing Kth-Order Voronoi Diagrams.” IEEE Transactions on Computers, vol. 36, no. 11, IEEE, 1987, pp. 1349–54, doi:10.1109/TC.1987.5009474.
Google Scholar