Institute of Software Technology

Delaunay Triangulations
Discrete and Computational Geometry
WS 2015/16

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 1

Institute of Software Technology

Yesterday
How many Delaunay triangulations can a point set have?
• Definition of the Delaunay graph
• Necessary and sufficient conditions for unique Delaunay
triangulations, examples with many Delaunay triang.

Why are we actually interested in Delaunay triangulations?

• Large Angles in Delaunay triangulations
• Some further properties of Delaunay triangulations

What if we need a triangulation with some non-Delaunay

edges, for example to model a river in a terrain?
• Constrained Delaunay triangulations
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 2
Institute of Software Technology

Today
How fast can we compute a Delaunay triangulation?
• Incrementally constructing Delaunay triangulations
• Divide and conquer algorithm: sketch

Some exercises around Delaunay triangulations

• Minimum spanning trees and Delaunay triangulations
• Minimum weight triangulations and Delaunay
triangulations
• Vertex degrees in Delaunay triangulations
• ...

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 3

Institute of Software Technology

Constructing Delaunay Triangulations

How fast can we compute a Delaunay triangulation?
Up to now: The Lawson Flip algorithm. O(n2 ) flips
1. Compute some arbitrary triangulation.
2. While there exists a subtriangulation of four points that
is not locally Delaunay, perform a Lawson flip.
Open: How and how fast can we find if and where to flip?
Alternative Idea: Insert points one after another.
• Maintain Delaunay triangulation DT (R) of the point set
R ∪ S inserted so far.
• When adding s, update DT (R) to obtain DT (R ∪ s).
• Start with a (laaarge) triangle of three extra points that
contains all points of S (and end with removing the
triangle) ⇒ No special cases, all insertions interior.
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 4
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).

Example:

∆
s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).

Example:

∆
s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).

Example:

s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).

Example:

s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).

Example:

s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is incident to s. { Why?
Example:

s
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is incident to s. { 
X
Corollary. Locating the edges that need to be flipped can
be done in constant time per edge.

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5

Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is in the Delaunay graph of R∪{s}.
Proof. C(∆)
Edges added in Step 2:
s
∆

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5

Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is in the Delaunay graph of R∪{s}.
Proof. C(∆)
Edges added in Step 2:
s
∆

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5

Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is in the Delaunay graph of R∪{s}.
Proof. C(∆)
Edges added in Step 2:
s
∆

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5

Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is in the Delaunay graph of R∪{s}.
Proof.
Edges added in Step 3:
s


X
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5
Institute of Software Technology

Adding a point to a Delaunay Triangulation

Steps for point insertion (point s interior of DT (R)):
1. Find the triangle ∆ of DT (R) that contains s.
2. Connect s to all vertices of ∆ to obtain a triangulation
T (R ∪ {s}) from DT (R).
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}).
Lemma. Every new edge is in the Delaunay graph of R∪{s}.
Corollary. The number of flips for adding a new point s to
DT (R) is d(s) − 3, where d(s) is the degree of s in the
resulting Delaunay triangulation DT (R ∪ {s}).
Next: How can we efficiently solve Step 1?

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 5

Institute of Software Technology

History Graph
For locating s in DT (R), we maintain a history graph:
• Its vertices are all triangles that have ever been created
during the incremental construction of DT (R).
• It contains a directed edge from ∆ to ∆0 whenever ∆
has been destroyed during the insertion of ∆0 .

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 6

Institute of Software Technology

Incremental Construction
How much in total?
Incrementally constucting a Delaunay triangulation DT (S):
• We add an initial triangle of extra points
History graph: first vertex Θ(1)
• for each point of S we ...
1. Find the triangle ∆ of DT (R) that contains s.
History graph: find unique path to leaf. per step Θ(1)
2. Connect s to all vertices of ∆ to obtain a
triangulation T (R ∪ {s}) from DT (R). Θ(1)
History graph: add 3 vertices + edges, dout (∆) = 3.
3. Make Lawson flips to transform T (R ∪ {s}) to a
Delaunay triangulation DT (R ∪ {s}). per flip Θ(1)
History graph: add 2 vertices + 4 edges per flip,
dout = 2 for every destroyed triangle.
• We remove the initial triangle and all incident edges. O(n)
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 7
Institute of Software Technology

Incremental Construction: Analysis

Problem 1. How many flips / fliptests per inserted point?
• d(s) − 3 flips if s has degree d(s) in DT (R ∪ {s}).
• 3 tests after inserting, ≤ 2 additional tests per flip.
• Trick: insert points in randomized order.
⇒ Expected degree: E(d(s)) < 6.
⇒ Expected number of flips and tests for flips: Θ(1).
⇒ Expected number of triangles created in total during
the construction: Θ(n).
⇒ Expected size of the history graph: Θ(n).
⇒ Expected total storage: Θ(n).

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 8

Institute of Software Technology

Incremental Construction: Analysis

Problem 2. How much time for locating the next point?
• History graph: every vertex has outdegree ≤ 3
⇒ Search time per step: Θ(1).
• Assume s is inserted as ith point and that p was inserted
before s as j th point (j < i) into DT (R).
⇒ Probability that the triangle for s in DT (R) is different
from the triangle ∆ for s in DT (R ∪ {p}):
Probability that p is a vertex of ∆ in DT (R ∪ {p}).
⇒ Triangle for s has changed with probability 3/j during
insertion of p. P3
⇒ Expected number of triangle changes ≤ 2 j = O(log i)
j<i
⇒ Expected total running time: O(n log n).
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 8
Institute of Software Technology

Incremental Construction: Analysis

Theorem. A Delaunay triangulation of any n-point set
in lR2 can be constructed incrementally in expected time
O(n log n) and with expected storage Θ(n). 
X
Question: What is the worst-case runtime and space of
this incremental algorithm?
Remark. It has been shown that any incremental con-
stuction algorithm for Delaunay triangulations needs Ω(n2 )
time in the worst case.
Question: What is a lower bound for the the worst-case
runtime of any Delaunay triangulation algorithm?

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 8

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Divide and Conquer

Recall the algorithm for convex hulls from the first lecture ...
... a similar approach works for Delaunay triangulations!
Merge: • create triangles with empty circumcircles
Merge: • remove conflicting edges
It can be shown that merging can be done in linear time.
Theorem. A Delaunay triangulation of any n-point set
in lR2 can be constructed in O(n log n) time.

Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 9

Institute of Software Technology

Conclusion
Delaunay triangulations can be computed efficiently
• Incremental construction in expected time O(n log n)
• Divide and conquer with determinsitic time O(n log n)
• More constructions later this course.

Delaunay triangulations are “nice”

• Maximize the smallest angle or even the angle vector
• Minimize the largest circumcircle
• Maximize the mean inradius
• tend to avoid narrow triangles
• More properties later this course and now: Exercises
Birgit Vogtenhuber 05.11.2015 Delaunay Triangulations 10