Voronoi
Tilings and Delaunay Triangulations| Voronoi
Tilings and Delaunay Triangulations |
Voronoi Tessellation > s.a. tiling.
* Idea: Given any locally
finite set of points {pi} in Euclidean
space, or manifold M with Riemannian metric, each pi defines
a cell given by
the set of all points in M which are closer to pi than any
other in the set; a.k.a. Dirichlet or Thiessen construction in 2D, 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, Vn*
and Vn, of which V1 = V1*
is the usual Voronoi tiling; Can also define
a
time-dependent type; If the nucleation is continuous, we get a fractal.
* Example, S2: 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 R3 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),
a0805 [2D and 3D perturbed regular lattices].
@ Random:
Tanemura www [2D-4D,
numerical]; Miles MB(70)-mr;
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]; > s.a. statistical
geometry,
random tiling.
@ 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 AAP(05); Baumstark
& Last AAP(07)
[properties of faces and neighbors].
@ Special manifolds: Isokawa AAP(00)
[3D hyperbolic spaces]; Na et al CG(02)
[on S2].
@ Generalizations: Miles & Maillardet JAProb(82)
[Vn].
@ 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].
> 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 Sn–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].
@ 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 R2].
@ Refinement: Shewchuk CG(02);
Rineau
& Yvinec CG(07).
In Physics > s.a. crystals [quasicrystals];
quantum systems; tiling.
@ 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.
@ Cosmology: Doroshkevich et al ap/96/A&AS;
Ramella et al A&A(01)ap [galaxy
clusters]; van de Weygaert ap/99-in,
ap/02-in, ap/02-in,
a0707-in [large-scale
structure].
@ Quantum gravity: Miller CQG(97)gq [Rc];
> s.a. regge calculus.
Main page – Abbreviations – Journals – Comments – Other
sites – Acknowledgements
Send feedback and suggestions to bombelli at olemiss.edu – Modified
21 may 2008