Transcript Slide 1

3. Delaunay triangulation
3.1 Euler’s formula
If a planar connected graph has e edges, f facets and v
vertices, than Euler’s formula states:
f - e + v = 1.
Similarly, for the numbers of edges, facets and vertices of a
simply connected * (“sphere like”) 3-dim. polyhedron holds:
f-e +v=2
(eq. 1)
*Every simple closed polygon p, consisting of its edges, disconnects its
surface: there are 2 facets of P such that every chain of adjacent facets,
connecting these two, crosses polygon p.
p
f1
f2
p
f1
Sphere like
f2
Delaunay triangulation (Euler’s formula cont.)
p
“Donut like”
By a theorem of Steiner, every graph having the properties
- every facet is a polygon,
- every edge is incident to exactly two facets,
- every vertex figure is a polygon,
- eq. 1 is satisfied,
can be realized as a convex polyhedron.
This is therefore also true for its dual graph. This duality can
be realized as polarity.
Delaunay triangulation (Euler’s formula cont.)
Euler’s formula gives rise to many relations between the
numbers e, f and v. By the theorem of Steiner and the
duality principle, every such relation holds also for the
numbers e, v and f .
Every facet of a polyhedron P has at least 3 edges. Summing
along facets, total number of edges is  3f . In this sum every
edge is counted twice (for two facets incident to it). Hence:
2e3f
2e3v
f 2v-4
v2f -4
e3v-6
e3f -6
(1), and dually
(2). The inequality (1) and Euler’s formula imply:
(3), and dually
(4). The inequality (3) and Euler’s formula imply:
(5), and dually
(6)...
Delaunay triangulation (Polygon)
3.2 Polygon: interior & exterior points, diagonals.
Every point X, not on the boundary of a simple polygon P, has
the property*:
Half lines through X not through a vertex of P intersect the
edges of P in an odd number of points, when X is said to be
an (interior) point of P, or in an even number of points,
when X is said to be an exterior point of P.
• Every polygon P has inner diagonal (having only inner points).
• An inner diagonal A i A k of P = A1A2…An divides the interior
of P into the interiors of the polygons P1 = A i A k A k+1 …
and P2 = A i A k A k-1 …
*This property, as well as many polygonal properties are not easy to prove!
Delaunay triangulation (Triangulation)
A k+1
3.3 Triangulation
I
E
A k-1
Ak
Ai
A consequence of the last two properties is that every simple
planar polygon admits a triangulation by its inner diagonals.
If the number of triangles is t, summing the edges by triangles
we get 3t=2d + n. By Euler’s formula is n - (n + d) + t = 1,
hence
t = n - 2 and d = n - 3.
Delaunay triangulation (Triangulation)
Hence, at least two triangles of the triangulation have two
sides of P as edges (each divide P into triangle and (n - 1) –
gon), otherwise the number of sides would have been  n-1.
This property is frequently used in inductive proofs:
Problem. Prove that the vertices of a triangulation of a
polygon P can be colored in 3 colors so that the vertices of
every triangle have different colors.
More generally:
A triangulation of a planar graph is its maximal, planar
edge-refinement. (Faces are triangles (1), no edge is free (2),
the boundary is a polygon (3), all vertices are used (4))
triangulation
Delaunay triangulation (Triangulation)
If such a triangulation has n vertices on the boundary and k
vertices in the interior, f triangles and e edges, a simple
counting + Euler’s formula shows:
f=2n- 2 -k
and
e = 3 n - 3 - k.
In some applications, e.g. in computer graphics, is important
that the triangles of a triangulation are not slim. Otherwise a
human eye will see them as dashes. To get the best result we
find the triangulation for which the angles of triangles are the
greatest possible. This requirement leads to the following
comparison:

Delaunay triangulation (Definition)
Let 1 , 2 , …,  3f be the ordered sequence of angles of all
the triangles of the triangulation 1 , i.e. let
1  2  …   3f
Let 1 , 2 , …,  3f is another such sequence corresponding
to some triangulation 2. We define ordering:
1  2 iff the corresponding sequences of numbers  i and  i
are equal, or  k <  k at the first index k where they disagree.
A Delaunay triangulation of a planar set of points
S is its triangulation which maximizes the previous
order relation.
Delaunay triangulation (Delaunay Graph)
3.4 Delaunay Graph and Voronoi Diagram
Voronoi Diagram of a finite planar point set S defines the
following unique dual graph, named Delaunay Graph:
Two points of S are joined by an edge if they define
neighboring facets of the Voronoi Diagram of S.
A
B
D
o
C
Voronoi Diagram
Delaunay Graph
Delaunay triangulation (Delaunay Graph)
Let ABCD be a cell of the Delaunay Graph. Border between
neighboring Voronoi Cells CA ,CB, A,B S (of the Voronoi
Diagram) consists of points equally distant to A and B, and to
which the other points of S are farther. It is therefore on the
bisector of [AB]. Hence, the vertex o of the Voronoi Diagram
common to neighb. cells of A, B, C and D is equally distant to A,
B, C, D and other points of S are farther:
A
circumscribed circle of ABCD
B
(a facet of the Delaunay Graph)
o
D
contains no other point of S.
Opposite ? (Exercise)
This leads to:
C
A subset of S defines a facet of the Delaunay Graph iff
the points of S are on a circle which contains (on and in it)
no other point of S.
Delaunay triangulation (Delaunay Graph)
3.5 Delaunay Triangulation and Delaunay Graph
We first give an algorithm which leads to a locally maximal
triangulation (a). Then we prove that this triangulation is a
triangulation of the Delaunay Graph of S (b).
(a)Let ABC, BCD be a pair of adjacent triangles of a triang. T.
If D is interior to the circumscribed circle of ABC, then the
substitution (flip) ABC,ACD  ABD,BDC leads to the
triangulation T’ with T  T’ ()*
Y
C
X
D
B
A
ACB = AXB < ADB,
CAB = CXB < CDB,
CAD < CAX = CBD,
ACD < ACX = ABD, 
*Among angles along diagonal is the smallest angle of a
triangulation. Since for each such angle of T, their is a
smaller one in T’, the inequality () holds.
Delaunay triangulation (Delaunay Graph)
(b) Iterating (a) we end up with a triangulation T* where all
circumscribed circles are with “empty” interior. Such a
triangulation T* is (see 3.4) a triangulation of the Delaunay
Graph of S. Hence:
Delaunay Triangulation is a refinement of the Delaunay Graph
If all facets of the Delaunay Graph are triangles, i.e. if the initial
set S is in general position (as we are going to assume further),
the algorithm is finished. If a facet of a Delaunay Graph is a
quadrangle, we easily optimize its triangulation :
d


d < d1
 < 1
1
d1
-How to triangulate a 5-gon?
- Is their an algorithm for a
general problem?
Delaunay triangulation (Algorithm6)
Back to the algorithm (case: all facets of the Delaunay Graph
are triangles.
By 2.3 Exercise 14a and 3.4, the facets of the Delaunay Graph
(circles …) are projected by  onto some facets of the Conv (S).
By 2.3 Exercise 14b and 3.4, these facets are the lower (wrt
z - axis) facets of Conv (S). We are ready for the Algorithm6.
Algorithm6. (Implementation = Exercise 18 ).
Step1=Step1 of the algorithm4.
Step 2. We calculate the lower “cap” of Conv (S).
Step 3. The Delaunay Graph of S is the vertical projection
of the lower cap of Conv (S) onto .
Delaunay triangulation (Algorithm7)
The idea described in 3.5a (local improvements alg.) leads to:
Algorithm 7. (Implementation = Exercise 19 ).
Step 1. The initial set S is surrounded with a sufficiently large
triangle which is the first triangle of the triangulation.
Step i+1.1 New point X of S is located ( § 4) in a triangle Ti of
the triangulation obtained in Step i. It separates Ti in 3 triangles.
The pairs of triangles to start local improvement (diagonal flip in
the corresponding 4-angle) are these 3 triangles with their
neighbors! Is that all?
?
Ti
X
OK
Tk
?
X
? Tk