Voronoi Tilings and Delaunay Triangulations| 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 page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 11 jan 2017