An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

Bernard Hazelle, Herbert Edelsbrunner

Research output: Contribution to journalArticlepeer-review

54 Scopus citations

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 languageEnglish (US)
Pages (from-to)1349-1354
Number of pages6
JournalIEEE Transactions on Computers
VolumeC-36
Issue number11
DOIs
StatePublished - Nov 1987
Externally publishedYes

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

Fingerprint Dive into the research topics of 'An Improved Algorithm for Constructing kth-Order Voronoi Diagrams'. Together they form a unique fingerprint.

Cite this