A lower bound on Voronoi diagram complexity

被引：10

作者：

Aronov, B ^{[1
]}

机构：

[1] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 83卷 / 04期

基金：

美国国家科学基金会;

关键词：

Voronoi diagram; computational geometry; computational complexity;

D O I：

10.1016/S0020-0190(01)00336-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A lower bound on Voronoi diagram complexity is presented. The Voronoi diagram is a classification of points of the ambient space according to the identity of the closest site or sites. Results provided evidence that the bound derived from envelope analysis is closer to the truth as the conjecture of Sharir does not hold.

引用

页码：183 / 185

页数：3

共 13 条

[1]

AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880

[2]

AURENHAMMER F, 1999, HDB COMPUTATIONAL GE

[3] Voronoi diagrams in higher dimensions under certain polyhedral distance functions [J].

Boissonnat, JD ;

Sharir, M ;

Tagansky, B ;

Yvinec, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 19 (04) :485-519

[4] Voronoi diagrams of lines in 3-space under polyhedral convex distance functions [J].

Chew, LP ;

Kedem, K ;

Sharir, M ;

Tagansky, B ;

Welzl, E .

JOURNAL OF ALGORITHMS, 1998, 29 (02) :238-255

[5] VORONOI DIAGRAMS AND ARRANGEMENTS [J].

EDELSBRUNNER, H ;

SEIDEL, R .

DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (01) :25-44

[6]

Edelsbrunner H., 1987, Algorithms in combinatorial geometry, V10

[7]

Fortune S., 1997, Handbook of discrete and computational geometry, P377

[8]

FORTUNE S, 1995, COMPUTING EUCLIDEAN, V4, P225

[9]

LEVEN D, 1987, ADV ROBOTICS, V1, P187

[10]

Sharir M, 1995, LECT NOTES COMPUT SC, V955, P109

← 1 2 →