An improved algorithm for constructing kth-order Voronoi diagrams

B. Chazelle, H. Edelsbrunner, IEEE Transactions on Computers 36 (1987) 1349–1354.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
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
Volume
36
Issue
11
Page
1349 - 1354
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, 36(11), 1349–1354. 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 36, no. 11 (1987): 1349–54. 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, 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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar