An improved algorithm for constructing kth-qrder voronoi diagrams

Bernard Chazelle, Herbert Edelsbrunner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

The kth-order Voronoi diagram of a set of points o 2 in E (called sites) subdivides E into maximal regions such that each point within a given region has 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 1n O{n2logn+k(n-k)log2n) time, 0(k(n-k)) storage, and O(n2+k(n-k)log2n) time,O(n) storage,.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages228-234
Number of pages7
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Externally publishedYes
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

NameProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/7/85

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Geometry and Topology

Fingerprint Dive into the research topics of 'An improved algorithm for constructing k<sup>th</sup>-qrder voronoi diagrams'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Edelsbrunner, H. (1985). An improved algorithm for constructing kth-qrder voronoi diagrams. In Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 (pp. 228-234). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323263