A note on visibility-constrained Voronoi diagrams

F. Aurenhammer; B. Su; Y. F. Xu; B. Zhu

doi:10.1016/j.dam.2014.04.009

A note on visibility-constrained Voronoi diagrams

F. Aurenhammer
, B. Su
, Y. F. Xu
, B. Zhu

School of Management

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

4 Scopus citations

Abstract

We consider a variant of visibility-constrained Voronoi diagrams for n given point sites in the Euclidean plane. Whereas such diagrams typically are of size Ω(n²), the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in n.

Original language	English
Pages (from-to)	52-56
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	174
DOIs	https://doi.org/10.1016/j.dam.2014.04.009
State	Published - 10 Sep 2014

Keywords

Line arrangement
Visibility
Voronoi diagram

Access to Document

10.1016/j.dam.2014.04.009

Cite this

@article{d9b3896c298141698f2a4e93106b8e0e,

title = "A note on visibility-constrained Voronoi diagrams",

abstract = "We consider a variant of visibility-constrained Voronoi diagrams for n given point sites in the Euclidean plane. Whereas such diagrams typically are of size Ω(n2), the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in n.",

keywords = "Line arrangement, Visibility, Voronoi diagram",

author = "F. Aurenhammer and B. Su and Xu, \{Y. F.\} and B. Zhu",

year = "2014",

month = sep,

day = "10",

doi = "10.1016/j.dam.2014.04.009",

language = "英语",

volume = "174",

pages = "52--56",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A note on visibility-constrained Voronoi diagrams

AU - Aurenhammer, F.

AU - Su, B.

AU - Xu, Y. F.

AU - Zhu, B.

PY - 2014/9/10

Y1 - 2014/9/10

N2 - We consider a variant of visibility-constrained Voronoi diagrams for n given point sites in the Euclidean plane. Whereas such diagrams typically are of size Ω(n2), the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in n.

AB - We consider a variant of visibility-constrained Voronoi diagrams for n given point sites in the Euclidean plane. Whereas such diagrams typically are of size Ω(n2), the combinatorial and algorithmic complexity of the studied variant is significantly subquadratic in n.

KW - Line arrangement

KW - Visibility

KW - Voronoi diagram

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

U2 - 10.1016/j.dam.2014.04.009

DO - 10.1016/j.dam.2014.04.009

M3 - 文章

AN - SCOPUS:84902264573

SN - 0166-218X

VL - 174

SP - 52

EP - 56

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A note on visibility-constrained Voronoi diagrams

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this