An improved algorithm for constructing kth-qrder voronoi diagrams

Bernard Chazelle; Herbert Edelsbrunner

doi:10.1145/323233.323263

An improved algorithm for constructing k^th-qrder voronoi diagrams

Bernard Chazelle, Herbert Edelsbrunner

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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)log²n) time, 0(k(n-k)) storage, and O(n²+k(n-k)log²n) time,O(n) storage,.

Original language	English (US)
Title of host publication	Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
Publisher	Association for Computing Machinery, Inc
Pages	228-234
Number of pages	7
ISBN (Electronic)	0897911636, 9780897911634
DOIs	https://doi.org/10.1145/323233.323263
State	Published - Jun 1 1985
Externally published	Yes
Event	1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States Duration: Jun 5 1985 → Jun 7 1985

Publication series

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

Other

Other	1st Annual Symposium on Computational Geometry, SCG 1985
Country/Territory	United States
City	Baltimore
Period	6/5/85 → 6/7/85

All Science Journal Classification (ASJC) codes

Computational Mathematics
Geometry and Topology

Access to Document

10.1145/323233.323263

Cite this

@inproceedings{22992d0b0dee4a5cad3ad9a92ddcee3e,

title = "An improved algorithm for constructing kth-qrder voronoi diagrams",

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,.",

author = "Bernard Chazelle and Herbert Edelsbrunner",

note = "Publisher Copyright: {\textcopyright} 1985 ACM.; 1st Annual Symposium on Computational Geometry, SCG 1985 ; Conference date: 05-06-1985 Through 07-06-1985",

year = "1985",

month = jun,

day = "1",

doi = "10.1145/323233.323263",

language = "English (US)",

series = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

publisher = "Association for Computing Machinery, Inc",

pages = "228--234",

booktitle = "Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985",

}

Chazelle, B & Edelsbrunner, H 1985, An improved algorithm for constructing k^th-qrder voronoi diagrams. in Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985. Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985, Association for Computing Machinery, Inc, pp. 228-234, 1st Annual Symposium on Computational Geometry, SCG 1985, Baltimore, United States, 6/5/85. https://doi.org/10.1145/323233.323263

An improved algorithm for constructing k^th-qrder voronoi diagrams. / Chazelle, Bernard; Edelsbrunner, Herbert.
Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985. Association for Computing Machinery, Inc, 1985. p. 228-234 (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - An improved algorithm for constructing kth-qrder voronoi diagrams

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

PY - 1985/6/1

Y1 - 1985/6/1

N2 - 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,.

AB - 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,.

UR - http://www.scopus.com/inward/record.url?scp=34250326311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250326311&partnerID=8YFLogxK

U2 - 10.1145/323233.323263

DO - 10.1145/323233.323263

M3 - Conference contribution

AN - SCOPUS:34250326311

T3 - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

SP - 228

EP - 234

BT - Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

PB - Association for Computing Machinery, Inc

T2 - 1st Annual Symposium on Computational Geometry, SCG 1985

Y2 - 5 June 1985 through 7 June 1985

ER -