Voronoi Tilings and Delaunay Triangulations  

Voronoi Tessellation > s.a. tilings.
* Idea: Given any locally finite set of points \(\{p_i^{~}\}\) in Euclidean space, or manifold \(M\) with Riemannian metric, each \(p_i^{~}\) defines a cell given by the set of all points in \(M\) which are closer to \(p_i^{~}\) than to any other in the set; a.k.a. Dirichlet or Thiessen construction in 2D, it generalizes the Wigner-Seitz construction for crystals, and is of interest in mineralogy, the cells representing single crystals grown from seeds located at the sites.
* Generalizations: Given a locally finite sprikling of a manifold with Riemannian metric, one can define two families of Voronoi-like tilings, \(V_n^*\) and \(V_n\), of which \(V_1^{~} = V_1^*\) is the usual Voronoi tiling; One can also define a time-dependent type; If the nucleation is continuous, we get a fractal.
* Example, S\(^2\): One can define a tiling either by a set of points (Delaunay or Voronoi), or by a set of great circles.
* Complexity: The number of vertices, edges, faces, ... of the Voronoi diagram; The complexity for a Voronoi diagram on \(n\) points can be as bad as O(n2), but if the points are chosen independently identically distributed uniformly from a region in \(\mathbb R^3\) or a 2D surface, then the expected complexity falls to O(n).
@ General references: Hinrichsen & Schliecker JPA(98)cm [scale-invariant fractal]; Held CG(01) [VRONI, comput]; Etzion & Rappoport CG(02) [of a polyhedron]; Golin & Na CG(03) [2D surface in 3D, complexity]; Lucarini JSP(08), JSP(09)-a0805 [2D and 3D perturbed regular lattices]; Voigt & Weis CAG-a1003 [3D]; Aurenhammer et al 13.
@ Random: Tanemura www [2D-4D, numerical]; Miles MB(70)-mr; Møller AAP(89); Møller 94; Grimm et al AdP(98)cm [energy spectra]; Calka AAP(03), AAP(03) [distribution of number of sides]; Hug et al AAP(04) [shape of large cells]; Zaninetti PLA(09) [and molecule aggregation]; Pimentel a1009 [properties of random Voronoi polyominoes]; > s.a. statistical geometry; random tilings.
@ Random, 1D: Khmaladze & Toronjadze AAP(01) [almost sure coverage property, non-homogeneous process].
@ Random, 2D, flat: Hayen & Quine AAP(00) [proportion of triangles], AAP(02) [areas]; Hilhorst JPA(06), JPA(07) [cell sidedness].
@ Random, 3D, flat: Ferenc & Néda PhyA(07) [and 2D, size distribution].
@ Random, flat, any dimension,: Muche & Stoyan JAProb(92) [contact and chord length distribution]; Muche AAP(05); Baumstark & Last AAP(07) [properties of faces and neighbors]; Alishahi & Sharifitabar AAP(08) [in high dimensionality, the variance of the volume of the typical cell tends to 0 exponentially]; Muche AAP(10) [contact distributions]; Yao AAP(10) [variances of volumes of intersections with given regions].
@ Special manifolds: Isokawa AAP(00) [3D hyperbolic spaces]; Na et al CG(02) [on S2].
@ Generalizations: Miles & Maillardet JAProb(82) [\(V_n\)]; Ferraro & Zaninetti PhyA(12) [2D thick Voronoi diagrams, statistics of area size]; > s.a. galaxy distribution [weighted Delaunay and Voronoi tessellations].
@ Related topics: Chiu et al AAP(96) [sectional tessellations]; Baccelli et al AAP(00) [Markov paths]; Goldman & Calka CRAS(01) [spectral function]; Fekete & Meijer CG(05) [1-round Voronoi game]; Ziherl & Kamien PRL(00)cm [entropy]; Borovkov & Odell AAP(07) [point removal and addition process]; Klein et al CG(09) [abstract Voronoi diagrams, axiomatic foundation]; Muche & Nieminen JMP(12) [and Wigner surmises]; Zhu et al PhyA(14) [effects of regularity].
> Online resources: Wikipedia page.

Delaunay Triangulation > s.a. tiling / Gabriel Graph; simplex [Delaunay polytopes].
* Idea: A simplicial complex obtained as a triangulation of (M, g) from a locally finite set of points pi in M; If M is n-dimensional, n + 1 points define a simplex iff the S\(^{n-1}\) through them contains no other points (in the higher-order case, no more than k other points – but the triangulation is not unique).
* Duality: The dual of a Voronoi tessellation is a Delaunay triangulation.
@ General references: Veech Top(97) [partitions]; Lemaire & Moreau CG(00) [multi-dimensional]; Cohen-Steiner et al CG(04) [from PL complex]; Sohler CG(05) [fast reconstruction]; Bose & Devroye CG(07) [2D random, stabbing number]; Aurenhammer et al 13.
@ In the Euclidean plane: Cui et al CG(11) [upper bound on stretch factor]; Bose et al CG(11) [stretch factor]; Aichholzer et al CG(13) [blocking Delaunay triangulations]; Abellanas et al IJCGA(13) [shortening the shortest path between two vertices].
@ Special manifolds: Leibon G&T(02) [of compact hyperbolic surfaces].
@ Generalization: Gudmundsson et al CG(02), CG(05) [higher-order]; Bandyopadhyay & Snoeyink CG(07) [almost-Delaunay simplices]; Dereudre JSP(08) [Gibbs Delaunay tessellations of \(\mathbb R^2\)]; in McDonald & Miller a0804-in [hybrid Voronoi-Delaunay lattice]; Silveira & van Kreveld CG(09) [higher-order constrained]; Bose et al CG(13) [k-Delaunay graphs, properties]; Charbonnier et al a1701 [in the complex plane, measure and random triangulations].
@ Refinement: Shewchuk CG(02); Rineau & Yvinec CG(07); Spielman et al IJCGA(07) [parallel Delaunay refinement algorithm].

In Physics and Other Applications > s.a. crystals [quasicrystals]; quantum systems [for Holevo capacity]; tilings.
@ Percolation: Benjamini & Schramm CMP(98); Pittet JPA(99) [percolation]; Bollobás & Riordan PTRF(06)m.PR/05 [2D, critical probability = 1/2].
@ Dynamical models, other: Serrano et al JPA(02) [fluid particle models]; Priolo et al PRB(92) [conductance]; Priebe Frank & Hart a0712; > s.a. fluids.
@ Cosmology: Doroshkevich et al A&AS(97)ap/96; Ramella et al A&A(01)ap [galaxy clusters]; van de Weygaert ap/99-conf, ap/02-conf, ap/02-proc, a0707-proc [large-scale structure]; Zaninetti SAJ(10)-a1012 [void statistics].
@ Quantum gravity: Miller CQG(97)gq [Regge calculus]; > s.a. regge calculus; semiclassical quantum gravity.
@ Computation: Steinberg et al ApJS(15)-a1408 [Voronoi-based scheme for parallel computations]; González A&C-a1601 [the parallel code PARAVT].

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 11 jan 2017