Forest-like abstract Voronoi diagrams in linear time

被引：5

作者：

Bohler, Cecilia ^{[1
]}

Klein, Rolf ^{[1
]}

Lingas, Andrzej ^{[2
]}

Liu, Chih-Hung ^{[1
]}

机构：

[1] Univ Bonn, Inst Comp Sci 1, Bonn, Germany

[2] Lund Univ, Dept Comp Sci, Lund, Sweden

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2018年 / 68卷

关键词：

Voronoi diagrams; General distance; Abstract Voronoi diagrams; Linear-time algorithms; Forest structures;

D O I：

10.1016/j.comgeo.2017.06.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Abstract Voronoi diagrams are a general framework covering many types of concrete diagrams for different types of sites or distance measures. Generalizing a famous result by Aggarwal et al. [1] we prove the following. Suppose it is known that inside a closed domain D the Voronoi diagram V (S) is a tree, and for each subset S' subset of S, a forest with one face per site. If the order of Voronoi regions of V(S) along the boundary of D is given, then V (S) inside D can be constructed in linear time. (c) 2017 Elsevier B.V. All rights reserved.

引用

页码：134 / 145

页数：12

共 13 条

[1] A LINEAR-TIME ALGORITHM FOR COMPUTING THE VORONOI DIAGRAM OF A CONVEX POLYGON
AGGARWAL, A
GUIBAS, LJ
SAXE, J
SHOR, PW
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) : 591 - 604
[2] [Anonymous], 1995, Davenport-Schinzel Sequences and Their Geometric Applications
[3] Aurenhammer F., 2013, Voronoi diagrams and Delaunay triangulations, V8
[4] Bohler C., 2014, P 26 CAN C COMP GEOM
[5] Bohler C., 2014, P 30 EUR WORKSH COMP
[6] Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
Dillencourt, MB
[J]. DISCRETE APPLIED MATHEMATICS, 1996, 64 (03) : 207 - 217
[7] Fortune, 1997, HDB DISCRETE COMPUTA, P377
[8] Khramtcova E., 2015, LNCS, V9472
[9] Klein R., 1994, Algorithms and Computation. 5th International Symposium, ISAAC '94 Proceedings, P11
[10] RANDOMIZED INCREMENTAL CONSTRUCTION OF ABSTRACT VORONOI DIAGRAMS
KLEIN, R
MEHLHORN, K
MEISER, S
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1993, 3 (03): : 157 - 184

← 1 2 →