The State of the Art of Voronoi Diagram Research

The notion of

Voronoi diagrams

refer to a conceptually simple geometric construct that is based on a finite set of points in a Euclidean space. Intuitively speaking, it is such a simple notion that it can be described to a non-specialist. Indeed even some social and cultural settings can be described that would convey the essence of the concept. Consider for instance a number of strangers who are standing still in a room at random locations. In what region of space can an individual freely move his/her arms without appearing to be impolite to the others? Without having a precise definition of this

personal space

, each individual would most likely have an intuitive notion of it. If each individual is reduced to a single point occupying a specific location in the room, the personal space of a particular point is its

Voronoi cell

, the set of all points that are closer to that point than to any of the other points. Each Voronoi cell is a polyhedral region. The Voronoi diagram of the set of points is the partitioning of the space into the collection of Voronoi cells, together with their boundaries.