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 -