Author(s): | Chazelle, Bernard; Edelsbrunner, Herbert |
Article Title: | An improved algorithm for constructing kth-order Voronoi diagrams |
Affiliation | |
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. |
Journal Title: | IEEE Transactions on Computers |
Volume: | 36 |
Issue | 11 |
ISSN: | 0018-9340 |
Publisher: | IEEE |
Date Published: | 1987-11-01 |
Start Page: | 1349 |
End Page: | 1354 |
DOI: | 10.1109/TC.1987.5009474 |
Open access: | no |