VORONOI DIAGRAMS - A SURVEY OF A FUNDAMENTAL GEOMETRIC DATA STRUCTURE

被引：166

作者：

AURENHAMMER, F

机构：

来源：

COMPUTING SURVEYS | 1991年 / 23卷 / 03期

关键词：

CELL COMPLEX; CLUSTERING; COMBINATORIAL COMPLEXITY; CONVEX HULL; CRYSTAL STRUCTURE; DIVIDE-AND-CONQUER; GEOMETRIC DATA STRUCTURE; GROWTH MODEL; HIGHER DIMENSIONAL EMBEDDING; HYPERPLANE ARRANGEMENT; K-SET; MOTION PLANNING; NEIGHBOR SEARCHING; OBJECT MODELING; PLANE-SWEEP; PROXIMITY; RANDOMIZED INSERTION; SPANNING TREE; TRIANGULATION;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a survey of the Voronoi diagram, one of the most fundamental data structures in computational geometry. It demonstrates the importance and usefulness of the Voronoi diagram in a wide variety of fields inside and outside computer science and surveys the history of its development. The paper puts particular emphasis on the unified exposition of its mathematical and algorithmic properties. Finally, the paper provides the first comprehensive bibliography on Voronoi diagrams and related structures.

引用

页码：345 / 405

页数：61

共 284 条

[41]

BERN MW, 1990, UNPUB PROVABLY GOOD

[42]

BESAG J, 1974, J ROY STAT SOC B MET, V36, P192

[43] The activity groups of euclidean space (Second essay) The groups with a finite fundamental area [J].