ABSTRACT
For a given set of sites inside an area, the Voronoi diagram is a partition of the area into regions of the same neighborship. The Voronoi diagram is used for solving numerous problems in many fields of science. In the 2D Euclidean plane the Voronoi diagram is represented by a planar graph that divides the plane into cells. This chapter concentrates on applications of Voronoi diagram to geometric problems in 2D and 3D. It presents a simple incremental construction approach as well as generalizations of the Voronoi diagram and the Delaunay triangulation. The chapter introduces the concept of constrained Voronoi diagrams and discusses the famous post office problem. It also present data structures for the nearest neighbor search based on the Voronoi diagram.
