These regions are called Voronoi cells. The Voronoi diagram of a set of points is dual to its Delaunay triangulation. It is named after Georgy Voronoi, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet).
Voronoi diagrams appear in many areas in science and technology and have diverse applications. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Voronoi diagrams have been the subject of extensive research during the last 35 years, and many algorithms for computing them have been published. However, these algorithms are for specific cases. They impose restrictions on either the space (often R2 or R3), the generators (distinct points, special shapes), the distance function (Euclidean or variations thereof) and more. Moreover, their implementation is not always simple and their success is not always guaranteed. We present an efficient and simple algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional. We allow infinitely many generators of a general form. The algorithm computes each of the Voronoi cells independently of the others, and to any required precision. It can be generalized to other settings, such as manifolds, graphs and convex distance functions.
Interactive Voronoi Diagram Generator
In this work we present an efficient algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional.
An Algorithm for Computing Voronoi Diagrams of General Generators in General Normed Spaces
