Abstract
The 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.
Original language | English (US) |
---|---|
Pages (from-to) | 1349-1354 |
Number of pages | 6 |
Journal | IEEE Transactions on Computers |
Volume | C-36 |
Issue number | 11 |
DOIs | |
State | Published - Nov 1987 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics
Keywords
- Arrangements of lines and planes
- Euclidean and projective space
- Voronoi diagrams
- computational geometry
- geometric transforms
- maintenance of convex hulls