Voronoi diagram

A Voronoi diagram , also Thiessen polygons or Dirichlet decomposition , is a decomposition of space into regions that are determined by a given set of points in space, here called centers. Each region is determined by exactly one center and includes all points in space which, in relation to the Euclidean metric, are closer to the center of the region than to any other center. Such regions are also known as Voronoi regions . The Voronoi diagram is created from all points that have more than one closest center and thus form the boundaries of the regions.

Voronoi diagrams are named after the mathematician Georgi Feodosjewitsch Voronoi , the alternative names are derived from Alfred H. Thiessen and Peter Gustav Lejeune Dirichlet .

Example of a Dirichlet decomposition for a given set of points

General

The radial growth from starting points generates Voronoi regions. This can, for example, model crystal or cell growth.

Voronoi diagrams are used in a wide variety of scientific fields such as biology , chemistry , meteorology , crystallography , architecture and other scientific disciplines such as algorithmic geometry and materials science . A special case of the Voronoi diagram in three-dimensional space is the Wigner-Seitz cell . Although already mentioned in 1644 by Descartes in his book Principia Philosophiae , they were first given a more precise mathematical analysis by Dirichlet and Voronoi. Voronoi diagrams can also be used as the decomposition of high-dimensional spaces. In the literature, the definition is mostly limited to two-dimensional real space.

Foam between two sheets of glass forms cells that resemble Voronoi regions.

Discoveries

Voronoi diagrams have been rediscovered several times.

1850	1908	1909	1911	1927	1933	1958	1965	1966	1985
Dirichlet	Voronoi	Boldyrew	Alfred H. Thiessen	Paul Niggli	Eugene Paul Wigner and Frederick Seitz	FC Frank and JS Kasper	GS Brown	R. Mead	Loius Hoofd
mathematics	mathematics	geology	meteorology	Crystallography	physics	physics	ecology	ecology	anatomy
Dirichlet decomposition			Thiessen polygons	Areas of Effect	Wigner-Seitz cells	Frank Kasper phases

definition

The Thiessen polygons or the Voronoi diagram consist of the entire space minus the Voronoi regions, which in relation to the Euclidean distance arise from all points of the space that are closer to the corresponding center than to all other centers. In two-dimensional terms, these can be viewed as the intersection of several open half-planes , which in turn are bounded by a bisector between two points of the centers.

Formally, a Voronoi region of the point , where a given set of points is given by ${\ displaystyle VR (p, S)}$ ${\ displaystyle p \ in S}$ ${\ displaystyle S}$ ${\ displaystyle \ mathbb {R} ^ {2}}$

{\ displaystyle VR (p, S) = \ bigcap _ {q \ in S \ setminus \ {p \}} D (p, q)}

,

where is defined as an open half-plane and through ${\ displaystyle D (p, q)}$

{\ displaystyle D (p, q) = \ {x \ in \ mathbb {R} ^ {2}: | px | <| qx | \}}

given is. You are now through all Voronoi regions

{\ displaystyle VR (S) = \ bigcup _ {p \ in S} VR (p, S)}

given, the Voronoi diagram is obtained by

{\ displaystyle V (S) = \ mathbb {R} ^ {2} \ setminus VR (S)}

Informally, this means that precisely the boundaries of the regions which themselves do not belong to them form the diagram or the polygons. The resulting polygons can be divided into Voronoi edges (edges of the polygon) and Voronoi nodes (corners of the polygon). All points on the Voronoi edges have the same distance to the points whose Voronoi region lies next to the edge. ${\ displaystyle p \ in S}$

Creation of the dual graph of a Thiessen polygon

duality

The Voronoi diagram behaves in a dual way to the Delaunay triangulation and is used to construct a correspondingly triangulated surface.

In order to calculate the Delaunay triangulation, the corresponding dual graph for the Voronoi diagram is formed. This is done by connecting the centers of the polygons with each other in such a way that an orthogonal line is drawn for each Voronoi edge , which connects the corresponding two centers with each other (see figure).

Polygon method

Thiessen polygons are used, among other things, for the cartographic representation of measured values . The polygon method is a non-statistical (i.e. comparatively simple) interpolation method in geostatistics for the simple representation of the spatial distribution of geo-referenced measurement data.

The basic assumption is that the similarity of the unknown value of a point in the area to the known measured value decreases with the distance from it, i.e. the further apart the data are, the more dissimilar. With the polygon method, this relationship is expressed in that each measured value is homogenized for a Thiessen polygon surrounding it, i.e. all estimated values within this polygon are identical to the respective measured value.

The method is a poor approximation of the observable reality, since sharp value jumps occur at the polygon boundaries; Smooth transitions between two measured values cannot be represented with this method. Due to this fact, the polygon method is again well suited for the areal distribution of discrete data, for example binary data (e.g. measured value: "Snowfall: yes / no").

algorithm

Colored Voronoi diagram with randomly distributed points in the plane

The calculation of a Voronoi diagram using the Delaunay triangulation is possible for any dimensions. In the following, an algorithm for the two-dimensional case is described, which can be extended analogously to higher dimensions. The calculation takes place in three steps. First of all, all given points in the plane are projected onto a (hyper) paraboloid in an additional dimension . The convex hull is calculated from the points obtained in this way . In a second step, all surfaces of the convex envelope whose surface normal points downward are projected back onto the original plane. The regions obtained in this way are the triangles of the Delaunay triangulation. In a last step, the circumcenters of all triangles are connected between adjacent triangles, which results in the desired edges of the Voronoi polygons. ${\ displaystyle x, y}$ ${\ displaystyle z}$ ${\ displaystyle (x, y, x ^ {2} + y ^ {2})}$

In three dimensions, the spheres' centers are to be connected to surfaces by corners of the Delaunay tetrahedron .

Pseudocode

Designations: points , Delaunay triangulation , convex hull , Voronoi diagram . ${\ displaystyle P}$ ${\ displaystyle DT (P)}$ ${\ displaystyle KH (P)}$ ${\ displaystyle V (P)}$

 1: Initialisiere leere Mengen P', DT(P) und V(P)
 2:
 3: //Berechnung der konvexen Hülle
 4: Für alle p = (px, py)  $\in$  P:
 5:    Füge p' = (px, py, px² + py²) zu P' hinzu
 6: Berechne KH(P') //Mit geeignetem Algorithmus
 7:
 8: //Berechnung der Delaunay-Triangulation
 9: Für alle Seiten s  $\in$  KH(P'):
10:    Falls Normalenvektor von s nach unten zeigt:
11:       Für alle Kanten k von s:
12:          Setze z-Wert von jedem Knoten  $\in$  k auf 0
13:          Erstelle neue Kante k' = k
14:          Füge k' zu DT(P) hinzu
15:
16: //Berechnung der Voronoi-Zellen
17: Für alle Dreiecke d in DT(P):
18:    Für alle an d angrenzenden Dreiecke d':
19:       Erstelle Kante m durch Verbindung der Umkreismittelpunkte von d und d'
20:       Füge m zu V(P) hinzu

To .

Applications

Humanities

In classical archeology or art history , the symmetry of statue heads is analyzed in order to determine the type of lost statue, such as B. on the 3D model of the head Sabouroff .

literature

Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu (Eds.): Spatial Tessallations: Concepts and Applications of Voronoi Diagrams . 2nd Edition. John Wiley & Sons, 2000, ISBN 978-0-471-98635-5 .
Franz Aurenhammer, Rolf Klein, Der-Tsai Lee: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore 2013, ISBN 9814447633 .

Web links

Commons : Voronoi diagrams - collection of images, videos and audio files

MathWorld (English)
Java applet for Voronoi diagrams
Another Java applet ( Memento from July 3, 2017 in the Internet Archive )
Cellular spatial structure, generated with the help of Voronoi (English)
Java applet that demonstrates the construction of a Voronoi diagram using the sweep line method ( Memento from December 8, 2012 in the web archive archive.today )

Individual evidence

↑ Rolf Klein: Algorithmische Geometrie , Springer 2005, ISBN 978-3-540-20956-0

↑ Thomas M. Liebling: Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twin . In: Documenta Mathematica . Extra Volume ISMP, 2012, p. 419–431 ( http://www.math.uiuc.edu/documenta/vol-ismp/60_liebling-thomas.pdf ( memento of August 9, 2017 in the Internet Archive ) ). Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twin ( Memento from August 9, 2017 in the Internet Archive )

↑ GS Brown: Point density in stems per acre (= NZ For. Res. Notes), Volume 38 1965, p. 11.

^ R. Mead: A Relationship between Individual Plant-spacing and Yield . In: Annals of Botany . 30, No. 2, April 1966, pp. 301-309.

^ Paul Niggli: XXIV. The topological structure analysis. I. In: Zeitschrift für Kristallographie . tape 65 , no. 1-6 , 1927, pp. 391-415 , doi : 10.1524 / zkri.1927.65.1.391 .

↑ John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4.8 MB)

↑ Tonio Hölscher , Susanne Krömker and Hubert Mara: The head Sabouroff in Berlin: Between archaeological observation and geometrical measurement . In: Benaki Museum (ed.): Commemorative publication for Georgios Despinis . Athens, Greece 2020.

↑ Voronoi Cells & Geodesic Distances - Sabouroff head on YouTube . Analysis with the GigaMesh software framework as in Hölscher et al. described, cf. doi: 10.11588 / heidok.00027985 .

[1] Rolf Klein: Algorithmische Geometrie , Springer 2005, ISBN 978-3-540-20956-0