Voronoi diagrams - a survey of a fundamental geometric data
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.
Reference: F. Aurenhammer.
Voronoi diagrams - a survey of a fundamental geometric data structure.
ACM Computing Surveys, 23(3):345-405, 1991.
Habilitationsschrift. [Report B 90-09, FU Berlin, Germany, 1990].