Voronoi and Delaunay graphs

The Voronoi diagram is one of the most fundamental and useful constructs defined by irregular lattices. As it is a widely-used geometrical construction, the diagram has several names. The construction is also known as Wigner-Seitz cells (metallurgy) or Blum's transform (biological shape and visual science). Although there is a broad spectrum of scientific disciplines that include interest in Voronoi diagrams, states that three aspects have been emphasized:

1. Their use in modeling natural phenomena.

2. The investigation of their mathematical, in particular, geometrical, combinatorial, and stochastic properties.


3. Their computer construction and representation. The Voronoi diagram is named after the mathematician M. G. Voronoi who explored this geometric construction in 1908. However, as early as in 1850 another mathematician, G. L. Dirichlet, studied the problem. Accordingly the Voronoi diagram is sometimes named Dirichlet tessellation.



Given N distinct points in Rn called generators or seeds. Each generator corresponds to a center of one region. The set of all points x that are closer to a given generator xi Î X than any other generator xj Î X j ¹ i is called Voronoi region of xi. Let d() be a distance function that implements the nearest neighbor criterion. The Voronoi region is then defined as:

V(i) = {x Î Rn : d(x,xi) y< d(x,xj) for all j ¹ i }

The union of the Voronoi regions of all xi Î X is called the Voronoi diagram of X:

Vor(X) = ÈV(i).

The Voronoi diagram is a partition (tessellation) of Rd into N polyhedral regions V(i) (Voronoi cells). d(x,xi) is usually the Euclidean distance function. (One can use different distance functions to define various forms of Voronoi diagrams, but we do not discuss them here.) The set of all Voronoi cells and their faces forms a cell complex. The vertices of this complex are called the Voronoi vertices, and the extreme rays (i.e. unbounded edges) are the Voronoi rays.

Appendix

Point C left of right of linear segment AB



Point D inside circle through A, B and C



Duality

a) Delaunay Diagram

b) Voronoi Diagram

Duality of Voronoi and Delaunay Diagram

Interpolation with Voronoi diagrams

Natural Neighbour Interpolation



Circumcircle of Tetrahedron





Voronoi Generators X: Set of points xi, i = 1,...,N

Voronoi Cell V(i) = {x e Rn : d(x, xi) < d(x, xj) for all j =/= i }

Voronoi diagram VOR(X) = noinU V(i)

The Voronoi diagram is a partition (tessellation) of Rd into

N polyhedral regions V(i) (Voronoi cells).

d(x,xi) is the Euclidean distance function.

Intersection of halfspaces defined by perpendicular bisecting hyperplanes between pairs of {P}



Definitions:

Convex Hull of set of Points: smallest convex set which contains these points

Convex Polytope P Convex Hull of a set of points in Rd



V-Representation:

Polytop representation by vertices

H-Representation:

Polytop representation by Halfspaces

P = {x | Ax <= b} A: m*d Matrix b: m-vector



Minkowski-Weyl theorem: A) and B) are equivalent

A) P is a polyhedron i.e. P={x: Ax <= b}

B) Finite vectors v1,v2,...vNsuch that P = conv(v1,....vN)A

Vertex enumeration problem: A-> B

Facet enumeration problem: B -> A



1D



Points have only one coordinate



Voronoi diagram consists of mid-point (Voronoi vertices) and line segments (Voronoi regions).





More dimensions

Convex Hull, Voronoi and Delaunay Diagrams

Generators: P = {-7,-4, 1,3,5};V.D.: Vor(P) = {-5.5,-1.5,2,4}

Equation of tangent:

So two adjacent tangents intersect at:

Lifting Map

Hyperplane

Unit Paraboloid

xd+1 = x12+...+xd2

Delaunay diagram: Lift d-dim generators

Lower convex hull

Voronoi diagram: Upper envelope of tangential hyperplanes

Lifting Map

Delaunay: S={(0,0), (2,1), (1,2),(4,0),(0,4),(4,4)}

CDD:

H: representation

x3 ³ 0

5 - 4x1 - 2x2 + x3 ³ 0

5 - 2x1 - 4x2 + x3 ³ 0

16 - 8x1 + x3 ³ 0

16 - 8x2 + x3 ³ 0

32 - 8x1 - 8x2 + x3 ³ 0



Volume of a Voronoi Polyhedron

Lasserre's recursive algorithm: H-representation

Voronoi Cell Decomposition in Tetrahedra

Properties of Delaunay Graphs



In preparation !!!

Walking Triangles



In preparation !!!

BACK

Counter Started 17-3-2004