An improved algorithm for constructing kth-order Voronoi diagrams Journal Article


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
IST Austria Authors