An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

Bernard Hazelle; Herbert Edelsbrunner

doi:10.1109/TC.1987.5009474

An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

Bernard Hazelle, Herbert Edelsbrunner

Research output: Contribution to journal › Article › peer-review

64 Scopus citations

Abstract

The kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E² subdivides E² 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(n² log n + k(n - k) log² n) time, O(k(n - k)) storage, and in O(n²+ k(n - k) log² n) time, O(n²) 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	https://doi.org/10.1109/TC.1987.5009474
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

Access to Document

10.1109/TC.1987.5009474

Cite this

@article{02a0909ef19e46f581eb9d094fcd07f0,

title = "An Improved Algorithm for Constructing kth-Order Voronoi Diagrams",

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

keywords = "Arrangements of lines and planes, Euclidean and projective space, Voronoi diagrams, computational geometry, geometric transforms, maintenance of convex hulls",

author = "Bernard Hazelle and Herbert Edelsbrunner",

year = "1987",

month = nov,

doi = "10.1109/TC.1987.5009474",

language = "English (US)",

volume = "C-36",

pages = "1349--1354",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

AU - Hazelle, Bernard

AU - Edelsbrunner, Herbert

PY - 1987/11

Y1 - 1987/11

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

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

KW - Arrangements of lines and planes

KW - Euclidean and projective space

KW - Voronoi diagrams

KW - computational geometry

KW - geometric transforms

KW - maintenance of convex hulls

UR - https://www.scopus.com/pages/publications/0023455982

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

U2 - 10.1109/TC.1987.5009474

DO - 10.1109/TC.1987.5009474

M3 - Article

AN - SCOPUS:0023455982

SN - 0018-9340

VL - C-36

SP - 1349

EP - 1354

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 11

ER -

An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this