Voronol Diagrams -A Survey of a Fundamental Geometric Data Structure

ACM Computing Surveys, ACM, Vol 23, Num 3, pp.345-405, September 1991

MESHING
RESEARCH
CORNER

Sandia National Laboratories
Albuquerque, New Mexico

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