Ch.9: Delaunay Triangulations

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 9.1. Triangulations of Planar Point Sets 9.2. The Delaunay Triangulation 9.3. Computing the Delaunay Triangulation 9.4. The Analysis 9.5. A Framework for Randomized Algorithms 9.6. Notes and Comments

85 flashcards · Mathematics · by lakesare

Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses

[Delaunay Triangulations] What is a terrain?
A surface in 3-space that every vertical line meets in at most one point: the graph of a function f:A⊂R2→Rf : A \subset \mathbb{R}^2 \to \mathbb{R}f:A⊂R2→R . f(p)f(p)f(p) is the height of the point ppp of the domain AAA .Good on a local scale; the earth is round, so not on a global one.
[Delaunay Triangulations] The height of a terrain is known only at a finite set PPP of sample points. How does the chapter approximate the terrain?
Triangulate PPP , then lift every sample point to its height, which maps every triangle to a triangle in 3-space. The result is a polyhedral terrain: the graph of a continuous, piecewise linear function. (Assigning every point the height of the nearest sample point instead gives a discrete terrain, which looks unnatural.)
[Delaunay Triangulations] Sample points on a mountain ridge are triangulated in two ways that differ in one flipped edge. In one, the point qqq between heights 980 and 990 gets height 985; in the other it gets height 23. What goes wrong in the second, and what criterion does the chapter derive from it?
qqq lies on an edge of two long, skinny triangles. Criterion: maximize the minimum angle. The height of qqq then comes from two far-apart points. Triangulation (b) cuts a valley through the ridge. Ties in the smallest angle are broken by the second smallest, and so on.
[Triangulations of Planar Point Sets] What is a maximal planar subdivision?
A planar subdivision S\mathcal{S}S to which no edge connecting two of its vertices can be added without destroying planarity. Any edge not in S\mathcal{S}S intersects an existing edge.
[Triangulations of Planar Point Sets] What is a triangulation of a point set PPP in the plane?
A maximal planar subdivision whose vertex set is PPP .
[Triangulations of Planar Point Sets] T\mathcal{T}T is a triangulation of a planar point set PPP (a maximal planar subdivision with vertex set PPP ). Why is every bounded face of T\mathcal{T}T a triangle?
A bounded face is a polygon, and every polygon can be triangulated, so a non-triangular face would admit one more edge (a diagonal), contradicting maximality.
[Triangulations of Planar Point Sets] In any triangulation T\mathcal{T}T of a planar point set PPP , what is the union of the bounded faces, and why?
The convex hull of PPP , because every segment between two consecutive points on the convex hull boundary is an edge of every triangulation. So the unbounded face is the complement of the convex hull. For terrains: the corners of the domain must be sample points so that the triangles cover the domain.
[Triangulations of Planar Point Sets] Theorem 9.1 PPP is a set of nnn points in the plane, not all collinear, and kkk points of PPP lie on the boundary of the convex hull of PPP . How many triangles and edges does every triangulation of PPP have?
2n−2−k\boldsymbol{2n - 2 - k}2n−2−k triangles and 3n−3−k\boldsymbol{3n - 3 - k}3n−3−k edges. kkk counts all points on the hull boundary, including points in the interior of hull edges, so kkk can exceed the number of hull vertices.
[Triangulations of Planar Point Sets] PPP : nnn points, not all collinear, kkk of them on the convex hull boundary. Every triangulation has 2n−2−k2n-2-k2n−2−k triangles and 3n−3−k3n-3-k3n−3−k edges.How does the proof get these numbers from a triangulation with mmm triangles?
Euler's formula n−ne+nf=2n - n_e + n_f = 2n−ne+nf=2 with nf=m+1n_f = m + 1nf=m+1 and ne=(3m+k)/2n_e = (3m + k)/2ne=(3m+k)/2 . Each triangle has 3 edges, the unbounded face has kkk , and each edge borders exactly two faces. Solving gives m=2n−2−km = 2n - 2 - km=2n−2−k , then ne=3n−3−kn_e = 3n - 3 - kne=3n−3−k .
[Triangulations of Planar Point Sets] 10 points in the plane, 4 of them on the convex hull boundary. How many triangles and edges does a triangulation have? And for nnn points in convex position?
14 triangles, 23 edges. In convex position: n−2n - 2n−2 triangles, 2n−32n - 32n−3 edges. 2n−2−k2n - 2 - k2n−2−k and 3n−3−k3n - 3 - k3n−3−k with k=4k = 4k=4 , resp. k=nk = nk=n .
[Triangulations of Planar Point Sets] What is the angle-vector A(T)A(\mathcal{T})A(T) of a triangulation T\mathcal{T}T with mmm triangles?
The 3m3m3m angles of the triangles of T\mathcal{T}T , sorted by increasing value: A(T)=(α1,…,α3m)A(\mathcal{T}) = (\alpha_1, \dots, \alpha_{3m})A(T)=(α1,…,α3m) with αi≤αj\alpha_i \le \alpha_jαi≤αj for i<ji < ji<j . All triangulations of the same point set have the same number mmm of triangles, so their angle-vectors have the same length.
[Triangulations of Planar Point Sets] Two triangulations T,T′\mathcal{T}, \mathcal{T}'T,T′ of the same point set have angle-vectors (α1,…,α3m)(\alpha_1, \dots, \alpha_{3m})(α1,…,α3m) and (α1′,…,α3m′)(\alpha'_1, \dots, \alpha'_{3m})(α1′,…,α3m′) . When is A(T)>A(T′)A(\mathcal{T}) > A(\mathcal{T}')A(T)>A(T′) , and when is T\mathcal{T}T angle-optimal?
A(T)>A(T′)A(\mathcal{T}) > A(\mathcal{T}')A(T)>A(T′) : lexicographically larger, i.e. some iii has αj=αj′\alpha_j = \alpha'_jαj=αj′ for all j<ij < ij<i and αi>αi′\alpha_i > \alpha'_iαi>αi′ . Angle-optimal: A(T)≥A(T′)A(\mathcal{T}) \ge A(\mathcal{T}')A(T)≥A(T′) for all triangulations T′\mathcal{T}'T′ of PPP . An angle-optimal triangulation exists since a point set has only finitely many triangulations.
[Triangulations of Planar Point Sets] Thales's Theorem CCC is a circle, the line ℓ\ellℓ meets CCC in aaa and bbb , and p,q,r,sp, q, r, sp,q,r,s lie on the same side of ℓ\ellℓ : p,qp, qp,q on CCC , rrr inside CCC , sss outside CCC . How do the angles ∡arb\measuredangle arb∡arb , ∡apb\measuredangle apb∡apb , ∡aqb\measuredangle aqb∡aqb , ∡asb\measuredangle asb∡asb compare?
∡arb>∡apb=∡aqb>∡asb\boldsymbol{\measuredangle arb > \measuredangle apb = \measuredangle aqb > \measuredangle asb}∡arb>∡apb=∡aqb>∡asb ∡pqr\measuredangle pqr∡pqr denotes the smaller angle defined by p,q,rp, q, rp,q,r .
[Triangulations of Planar Point Sets] What is an edge flip of the edge e=pipj‾e = \overline{p_ip_j}e=pipj in a triangulation T\mathcal{T}T , and when is it possible?
Remove pipj‾\overline{p_ip_j}pipj and insert pkpl‾\overline{p_kp_l}pkpl , where pipjpkp_ip_jp_kpipjpk and pipjplp_ip_jp_lpipjpl are the two triangles incident to eee . Possible when these two triangles form a convex quadrilateral. Only six angles of the angle-vector change: α1,…,α6\alpha_1, \dots, \alpha_6α1,…,α6 become α1′,…,α6′\alpha'_1, \dots, \alpha'_6α1′,…,α6′ .
[Triangulations of Planar Point Sets] When is an edge eee of a triangulation illegal?
When flipping eee increases the smallest of the six affected angles: min⁡1≤i≤6αi<min⁡1≤i≤6αi′\displaystyle\min_{1 \le i \le 6} \alpha_i < \min_{1 \le i \le 6} \alpha'_i1≤i≤6minαi<1≤i≤6minαi′ . α1,…,α6\alpha_1, \dots, \alpha_6α1,…,α6 are the angles of the two triangles incident to eee before the flip, α1′,…,α6′\alpha'_1, \dots, \alpha'_6α1′,…,α6′ after it.
[Triangulations of Planar Point Sets] Observation 9.3. T\mathcal{T}T has an illegal edge eee , and T′\mathcal{T}'T′ is obtained by flipping eee . How do the angle-vectors compare, and why?
A(T′)>A(T)\boldsymbol{A(\mathcal{T}') > A(\mathcal{T})}A(T′)>A(T) Only six angles change, and the smallest of them increases; so the first position where the sorted vectors differ is larger in A(T′)A(\mathcal{T}')A(T′) .
[Triangulations of Planar Point Sets] Lemma 9.4. The edge pipj‾\overline{p_ip_j}pipj is incident to triangles pipjpkp_ip_jp_kpipjpk and pipjplp_ip_jp_lpipjpl , and CCC is the circle through pi,pj,pkp_i, p_j, p_kpi,pj,pk . When is pipj‾\overline{p_ip_j}pipj illegal?
If and only if plp_lpl lies in the interior of CCC . Proved with Thales's Theorem; no angles need to be computed. The test is symmetric: plp_lpl is inside the circle through pi,pj,pkp_i, p_j, p_kpi,pj,pk iff pkp_kpk is inside the circle through pi,pj,plp_i, p_j, p_lpi,pj,pl .
[Triangulations of Planar Point Sets] pi,pj,pk,plp_i, p_j, p_k, p_lpi,pj,pk,pl form a convex quadrilateral, triangulated by either pipj‾\overline{p_ip_j}pipj or pkpl‾\overline{p_kp_l}pkpl . How many of these two edges are illegal (a) if the four points are not cocircular, (b) if they lie on a common circle?
(a) Exactly one. (b) Neither: both are legal. Illegal means the fourth point lies inside the circle through the other three, which happens for exactly one of the two diagonals unless all four are on one circle.
[Triangulations of Planar Point Sets] Why can an illegal edge always be flipped?
The two triangles incident to an illegal edge always form a convex quadrilateral. A flip needs a convex quadrilateral; otherwise the new edge would leave the union of the two triangles.
[Triangulations of Planar Point Sets] What is a legal triangulation, and how does it relate to angle-optimal triangulations?
A triangulation without illegal edges. Every angle-optimal triangulation is legal. Flipping an illegal edge would increase the angle-vector.
[Triangulations of Planar Point Sets] What does algorithm LegalTriangulation (T)(\mathcal{T})(T) do, and why does it terminate?
Flip illegal edges until none is left. It terminates because every flip increases the angle-vector. A point set has only finitely many triangulations. The output is a legal triangulation. It is too slow to be interesting, but the chapter's algorithm uses a similar flipping procedure.
[The Delaunay Triangulation] PPP is a set of sites in the plane with Voronoi diagram Vor⁡(P)\operatorname{Vor}(P)Vor(P) . What is the dual graph G\mathcal{G}G of Vor⁡(P)\operatorname{Vor}(P)Vor(P) ?
One node per Voronoi cell (i.e. per site), and an arc between two nodes when their cells share an edge. So G\mathcal{G}G has an arc for every edge of Vor⁡(P)\operatorname{Vor}(P)Vor(P) , and its bounded faces correspond one-to-one to the vertices of Vor⁡(P)\operatorname{Vor}(P)Vor(P) .
[The Delaunay Triangulation] What is the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) of a point set PPP ?
The straight-line embedding of the dual graph of Vor⁡(P)\operatorname{Vor}(P)Vor(P) : the node of the cell V(p)\mathcal{V}(p)V(p) is the point ppp , and the arc between V(p)\mathcal{V}(p)V(p) and V(q)\mathcal{V}(q)V(q) is the segment pq‾\overline{pq}pq . Dashed: Vor⁡(P)\operatorname{Vor}(P)Vor(P) . Named after the Russian mathematician Boris Delone, whose work was published in French.
[The Delaunay Triangulation] Theorem 9.5. What does the chapter prove first about the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) of a planar point set PPP ?
It is a plane graph: no two of its edges cross.
[The Delaunay Triangulation] Which property of Voronoi edges characterizes when pipj‾\overline{p_ip_j}pipj is an edge of the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) ?
pipj‾∈DG(P)\overline{p_ip_j} \in \mathcal{DG}(P)pipj∈DG(P) iff some closed disc CijC_{ij}Cij has pi,pjp_i, p_jpi,pj on its boundary and contains no other site of PPP . The center of such a disc lies on the common edge of the Voronoi cells V(pi)\mathcal{V}(p_i)V(pi) and V(pj)\mathcal{V}(p_j)V(pj) .
[The Delaunay Triangulation] pipj‾\overline{p_ip_j}pipj is a Delaunay edge iff some closed disc CijC_{ij}Cij has pi,pjp_i, p_jpi,pj on its boundary and no other site in it; its center lies on the common edge of the Voronoi cells V(pi),V(pj)\mathcal{V}(p_i), \mathcal{V}(p_j)V(pi),V(pj) .Why can two Delaunay edges pipj‾\overline{p_ip_j}pipj and pkpl‾\overline{p_kp_l}pkpl not cross?
A crossing would force an edge of the triangle tijt_{ij}tij to cross an edge of tklt_{kl}tkl , but these edges lie in disjoint Voronoi cells. tijt_{ij}tij has vertices pi,pjp_i, p_jpi,pj and the center of CijC_{ij}Cij ; its edge from pip_ipi to the center lies in V(pi)\mathcal{V}(p_i)V(pi) . pk,plp_k, p_lpk,pl lie outside CijC_{ij}Cij , hence outside tijt_{ij}tij , so a crossing pkpl‾\overline{p_kp_l}pkpl must cross an edge of tijt_{ij}tij incident to the center; symmetrically f…
[The Delaunay Triangulation] vvv is a vertex of Vor⁡(P)\operatorname{Vor}(P)Vor(P) where the cells of p1,…,pkp_1, \dots, p_kp1,…,pk meet. What is the corresponding face fff of the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) ?
A convex kkk -gon with vertices p1,…,pkp_1, \dots, p_kp1,…,pk , all on a circle around vvv .
[The Delaunay Triangulation] In this chapter, when is a point set in general position, and what does that imply for the Delaunay graph?
No four points lie on a circle. Then all Voronoi vertices have degree 3, so all bounded faces of DG(P)\mathcal{DG}(P)DG(P) are triangles. Random points are in general position with probability close to 1.
[The Delaunay Triangulation] What is a Delaunay triangulation of PPP , and when is it unique?
Any triangulation obtained by adding edges to DG(P)\mathcal{DG}(P)DG(P) . Unique iff DG(P)\mathcal{DG}(P)DG(P) is already a triangulation. DG(P)\mathcal{DG}(P)DG(P) is the Delaunay graph. It is a triangulation e.g. when PPP is in general position (no four points cocircular). Adding the edges is easy since all faces of DG(P)\mathcal{DG}(P)DG(P) are convex.
[The Delaunay Triangulation] Theorem 9.6 (i). When are three points pi,pj,pk∈Pp_i, p_j, p_k \in Ppi,pj,pk∈P vertices of the same face of the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) ?
If and only if the circle through pi,pj,pkp_i, p_j, p_kpi,pj,pk contains no point of PPP in its interior.
[The Delaunay Triangulation] Theorem 9.6 (ii). When do two points pi,pj∈Pp_i, p_j \in Ppi,pj∈P form an edge of the Delaunay graph DG(P)\mathcal{DG}(P)DG(P) ?
If and only if some closed disc contains pip_ipi and pjp_jpj on its boundary and no other point of PPP .
[The Delaunay Triangulation] Theorem 9.7. T\mathcal{T}T is a triangulation of PPP . When is T\mathcal{T}T a Delaunay triangulation?
If and only if the circumcircle of every triangle of T\mathcal{T}T contains no point of PPP in its interior.
[The Delaunay Triangulation] Theorem 9.8. How are legal triangulations (no edge whose flip increases the smallest of the affected angles) and Delaunay triangulations related?
A triangulation of PPP is legal if and only if it is a Delaunay triangulation of PPP . Delaunay ⇒\Rightarrow⇒ legal is immediate: empty circumcircles mean no edge fails the incircle test.
[The Delaunay Triangulation] Edge pipj‾\overline{p_ip_j}pipj with incident triangles pipjpkp_ip_jp_kpipjpk , pipjplp_ip_jp_lpipjpl is illegal iff plp_lpl is inside the circle through pi,pj,pkp_i, p_j, p_kpi,pj,pk . A triangulation is Delaunay iff no triangle's circumcircle has a point of PPP in its interior.Proof that every legal triangulation T\mathcal{T}T is Delaunay: assume some circumcircle C(pipjpk)C(p_ip_jp_k)C(pipjpk) contains a point plp_lpl . Which pair is chosen, and…
The pair (triangle pipjpkp_ip_jp_kpipjpk , point plp_lpl in its circumcircle) maximizing ∡piplpj\measuredangle p_ip_lp_j∡piplpj ; the triangle pipjpmp_ip_jp_mpipjpm across eee gives a larger angle. e=pipj‾e = \overline{p_ip_j}e=pipj is the edge of pipjpkp_ip_jp_kpipjpk separating it from plp_lpl . eee is legal, so pm∉C(pipjpk)p_m \notin C(p_ip_jp_k)pm∈/C(pipjpk) ; hence C(pipjpm)C(p_ip_jp_m)C(pipjpm) contains the part of C(pipjpk)C(p_ip_jp_k)C(pipjpk) beyond eee , so…
[The Delaunay Triangulation] Theorem 9.9. What is the relation between angle-optimal triangulations and Delaunay triangulations of PPP ?
Every angle-optimal triangulation is a Delaunay triangulation, and every Delaunay triangulation maximizes the minimum angle over all triangulations of PPP . Angle-optimal ⇒\Rightarrow⇒ legal ⇒\Rightarrow⇒ Delaunay.
[The Delaunay Triangulation] How many legal / angle-optimal triangulations does PPP have (a) in general position, (b) when four or more points can be cocircular?
(a) Exactly one, the Delaunay triangulation. (b) All Delaunay triangulations are legal, not all are angle-optimal. In (a) the Delaunay triangulation equals DG(P)\mathcal{DG}(P)DG(P) . In (b) all Delaunay triangulations have the same minimum angle: by Thales's Theorem, all triangulations of a set of cocircular points have the same minimum angle, so it doesn't matter how the faces of DG(P)\mathcal{DG}(P)DG(P) are triangulated.
[Computing the Delaunay Triangulation] How could a Delaunay triangulation of PPP be computed with the tools of the Voronoi diagram chapter, and which different approach does this chapter take?
Compute Vor⁡(P)\operatorname{Vor}(P)Vor(P) , read off DG(P)\mathcal{DG}(P)DG(P) , triangulate its faces with more than three vertices. This chapter: a randomized incremental algorithm computing it directly. The same approach as for linear programming and for trapezoidal maps.
[Computing the Delaunay Triangulation] How does the randomized incremental Delaunay algorithm start, before inserting any point of PPP ?
With one big triangle p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 containing PPP , where p0p_0p0 is the highest point of PPP and p−1,p−2p_{-1}, p_{-2}p−1,p−2 are two extra points far away. p0p_0p0 is the lexicographically highest point: largest yyy -coordinate, rightmost among those. It computes a Delaunay triangulation of P∪{p−1,p−2}P \cup \{p_{-1}, p_{-2}\}P∪{p−1,p−2} and finally discards p−1,p−2p_{-1}, p_{-2}p−1,p−2 with their incident edges.
[Computing the Delaunay Triangulation] The Delaunay algorithm adds two extra points p−1,p−2p_{-1}, p_{-2}p−1,p−2 to PPP and discards them at the end. Which condition must they satisfy?
They must not lie in any circle defined by three points of PPP , so that they destroy no triangle of the Delaunay triangulation of PPP .
[Computing the Delaunay Triangulation] Randomized incremental Delaunay triangulation: what happens when the next point prp_rpr (of a random permutation) is inserted?
Split the triangle containing prp_rpr into 3 (or, if prp_rpr is on an edge, the two triangles sharing it into 4), then call LegalizeEdge on the outer edges. After the split the triangulation need not be Delaunay: the new point can make existing edges illegal.
[Computing the Delaunay Triangulation] What does LegalizeEdge (pr,pipj‾,T)(p_r, \overline{p_ip_j}, \mathcal{T})(pr,pipj,T) do? ( prp_rpr is the point just inserted, pipj‾\overline{p_ip_j}pipj an edge of a triangle prpipjp_rp_ip_jprpipj .)
If pipj‾\overline{p_ip_j}pipj is illegal: flip it to prpk‾\overline{p_rp_k}prpk , where pipjpkp_ip_jp_kpipjpk is the triangle on the other side, and recurse on pipk‾\overline{p_ip_k}pipk and pkpj‾\overline{p_kp_j}pkpj . Dashed: the new edge prpk‾\overline{p_rp_k}prpk . The two recursive calls test the edges that became adjacent to prp_rpr .
[Computing the Delaunay Triangulation] After inserting prp_rpr into a Delaunay triangulation, which edges can have become illegal?
Only edges of triangles that changed: an edge legal before can only become illegal if one of its incident triangles changed. So only the edges of the new triangles need checking, which is what the calls of LegalizeEdge do.
[Computing the Delaunay Triangulation] Lemma 9.10. Every new edge created while inserting prp_rpr (by the split or by LegalizeEdge) is an edge of what?
Of the Delaunay graph of {p−2,p−1,p0,…,pr}\{p_{-2}, p_{-1}, p_0, \dots, p_r\}{p−2,p−1,p0,…,pr} . All new edges are incident to prp_rpr (grey: destroyed and created triangles). So every new edge is legal and never needs testing.
[Computing the Delaunay Triangulation] Lemma 9.10: every edge created while inserting prp_rpr is an edge of the Delaunay graph of {p−2,…,pr}\{p_{-2}, \dots, p_r\}{p−2,…,pr} . A segment is a Delaunay edge iff some disc has its endpoints on the boundary and no other point inside.Why is the split edge prpi‾\overline{p_rp_i}prpi (from prp_rpr to a vertex of the containing triangle pipjpkp_ip_jp_kpipjpk ) a Delaunay edge?
Shrink the circumcircle CCC of pipjpkp_ip_jp_kpipjpk to a circle C′⊂CC' \subset CC′⊂C through pip_ipi and prp_rpr ; C′C'C′ is empty. pipjpkp_ip_jp_kpipjpk was a Delaunay triangle before prp_rpr was added, so CCC contains no earlier point ptp_tpt , t<rt < rt<r , in its interior.
[Computing the Delaunay Triangulation] Lemma 9.10: every edge created while inserting prp_rpr is an edge of the Delaunay graph of {p−2,…,pr}\{p_{-2}, \dots, p_r\}{p−2,…,pr} . A segment is a Delaunay edge iff some disc has its endpoints on the boundary and no other point inside.A flip replaces pipj‾\overline{p_ip_j}pipj of the triangle pipjplp_ip_jp_lpipjpl by prpl‾\overline{p_rp_l}prpl . Why is prpl‾\overline{p_rp_l}prpl a Delaunay edge?
The circumcircle CCC of pipjplp_ip_jp_lpipjpl contains prp_rpr and no other point; shrink it to an empty circle C′⊂CC' \subset CC′⊂C with only prp_rpr and plp_lpl on its boundary. pipjplp_ip_jp_lpipjpl was a Delaunay triangle before prp_rpr was added, and CCC contains prp_rpr since otherwise pipj‾\overline{p_ip_j}pipj would not be illegal.
[Computing the Delaunay Triangulation] Why does the randomized incremental Delaunay algorithm (insert prp_rpr , split, LegalizeEdge on the new outer edges) end with a Delaunay triangulation?
New edges are Delaunay edges, hence legal, and LegalizeEdge tests every other edge whose triangles changed. Only edges of changed triangles can become illegal, and a legal triangulation is Delaunay. It can't loop forever: every flip increases the angle-vector.
[Computing the Delaunay Triangulation] What is the point location structure D\mathcal{D}D of the randomized incremental Delaunay algorithm?
A DAG whose leaves are the triangles of the current triangulation and whose internal nodes are triangles destroyed earlier. Cross-pointers link leaves and triangles. It starts as a single leaf for p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 .
[Computing the Delaunay Triangulation] How is the point location DAG D\mathcal{D}D (leaves = current triangles) updated (a) when a triangle is split, (b) when an edge flip replaces two triangles by two new ones?
(a) The leaf of the split triangle becomes an internal node with pointers to the 3 (or 2) new leaves. (b) Both old nodes get pointers to the two new leaves. Inserting prp_rpr into Δ1\Delta_1Δ1 , then flipping two edges. A node gets at most three outgoing pointers.
[Computing the Delaunay Triangulation] How is the next point prp_rpr located in the point location DAG D\mathcal{D}D of the Delaunay algorithm, and what does it cost?
Descend from the root to a child whose triangle contains prp_rpr , down to a leaf. Cost: linear in the number of triangles in D\mathcal{D}D containing prp_rpr . The root is p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 . Out-degree is at most 3, so each node on the search path costs O(1)O(1)O(1) .
[Computing the Delaunay Triangulation] Why are the extra points p−1,p−2p_{-1}, p_{-2}p−1,p−2 of the Delaunay algorithm treated symbolically?
To avoid the huge coordinates needed to place them far enough away. No coordinates are assigned; the point location and legality tests are modified to work as if the points were very far away.
[Computing the Delaunay Triangulation] Where are the symbolic points p−1p_{-1}p−1 and p−2p_{-2}p−2 conceptually placed?
p−1p_{-1}p−1 far right on a horizontal line below PPP ; p−2p_{-2}p−2 far left on a horizontal line above PPP . p−1p_{-1}p−1 lies outside every circle through three non-collinear points of PPP , and p−2p_{-2}p−2 outside every such circle of P∪{p−1}P \cup \{p_{-1}\}P∪{p−1} . Also: the clockwise order of PPP around p−1p_{-1}p−1 and the counterclockwise order of P∪{p−1}P \cup \{p_{-1}\}P∪{p−1} around p−2p_{-2}p−2 equal the lexicographic order. ppp is higher than qqq if yp>yqy_p > y_qyp>yq…
[Computing the Delaunay Triangulation] What is the Delaunay triangulation of P∪{p−1,p−2}P \cup \{p_{-1}, p_{-2}\}P∪{p−1,p−2} , where p−1p_{-1}p−1 is far right and lower than PPP , p−2p_{-2}p−2 far left and higher than PPP ?
That of PPP , plus p−1p_{-1}p−1 joined to the right convex hull of PPP , p−2p_{-2}p−2 to the left convex hull, and p−1p−2‾\overline{p_{-1}p_{-2}}p−1p−2 . The lowest point and the highest point p0p_0p0 of PPP are connected to both.
[Computing the Delaunay Triangulation] During point location, the position of pjp_jpj relative to the oriented line from pip_ipi to p−1p_{-1}p−1 or from p−2p_{-2}p−2 to pip_ipi is needed. How is it decided without coordinates for p−1,p−2p_{-1}, p_{-2}p−1,p−2 ?
pjp_jpj is to the left of either line iff pjp_jpj is lexicographically larger than pip_ipi .
[Computing the Delaunay Triangulation] Delaunay algorithm with symbolic points p−1,p−2p_{-1}, p_{-2}p−1,p−2 : how is the legality of pipj‾\overline{p_ip_j}pipj tested, where pk,plp_k, p_lpk,pl are the other vertices of its two triangles?
Edge of p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 : always legal. All of i,j,k,l≥0i, j, k, l \ge 0i,j,k,l≥0 : the usual incircle test. Otherwise: legal iff min⁡(k,l)<min⁡(i,j)\min(k, l) < \min(i, j)min(k,l)<min(i,j) . If exactly one index is negative, that point lies outside the circle through the other three. If min⁡(i,j)\min(i,j)min(i,j) and min⁡(k,l)\min(k,l)min(k,l) are both negative, use that p−2p_{-2}p−2 is outside every circle through three points of P∪{p−1}P \cup \{p_{-1}\}P∪{p−1} .
[The Analysis] What is the structural change of a randomized incremental algorithm such as the Delaunay algorithm?
The number of triangles created and deleted during the algorithm.
[The Analysis] Lemma 9.11. What is the expected number of triangles created by the randomized incremental Delaunay algorithm on nnn points (plus p0p_0p0 )?
At most 9n+1\boldsymbol{9n + 1}9n+1 . 1 for the starting triangle p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 , and at most 9 expected per insertion.
[The Analysis] Delaunay algorithm: after inserting prp_rpr , there are kkk Delaunay edges incident to prp_rpr . At most how many triangles were created, and why?
2k−3\boldsymbol{2k - 3}2k−3 , i.e. 2(k−3)+32(k - 3) + 32(k−3)+3 . The split creates 3 triangles and 3 edges at prp_rpr ; each flip creates 2 triangles and 1 more edge at prp_rpr . (Splitting on an edge: 4 and 4.)
[The Analysis] Pr={p1,…,pr}P_r = \{p_1, \dots, p_r\}Pr={p1,…,pr} and DGr=DG({p−2,p−1,p0}∪Pr)\mathcal{DG}_r = \mathcal{DG}(\{p_{-2}, p_{-1}, p_0\} \cup P_r)DGr=DG({p−2,p−1,p0}∪Pr) . Inserting prp_rpr creates at most 2deg⁡(pr,DGr)−32\deg(p_r, \mathcal{DG}_r) - 32deg(pr,DGr)−3 triangles.By backwards analysis, why is the expected degree of prp_rpr in DGr\mathcal{DG}_rDGr at most 6?
DGr\mathcal{DG}_rDGr is planar with r+3r + 3r+3 vertices: at most 3(r+3)−63(r + 3) - 63(r+3)−6 edges, 3 of them edges of p0p−1p−2p_0p_{-1}p_{-2}p0p−1p−2 . So the vertices of PrP_rPr have total degree <2[3(r+3)−9]=6r< 2[3(r+3) - 9] = 6r<2[3(r+3)−9]=6r , and prp_rpr is a random element of PrP_rPr . Hence E[triangles created in step r]≤2⋅6−3=9E[\text{triangles created in step } r] \le 2 \cdot 6 - 3 = 9E[triangles created in step r]≤2⋅6−3=9 .
[The Analysis] Theorem 9.12. Expected running time and storage of the randomized incremental algorithm for the Delaunay triangulation of nnn points?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) expected time, O(n)\boldsymbol{O(n)}O(n) expected storage.
[The Analysis] Randomized incremental Delaunay algorithm: why is the expected storage O(n)O(n)O(n) , and why is the expected time without point location O(n)O(n)O(n) ?
Both are proportional to the number of created triangles, which is O(n)O(n)O(n) in expectation (at most 9n+19n + 19n+1 ). Only the point location DAG D\mathcal{D}D could exceed linear storage, and each of its nodes is a created triangle.
[The Analysis] In what two ways can the Delaunay algorithm destroy a triangle pipjpkp_ip_jp_kpipjpk ?
A new point plp_lpl is inserted inside (or on the boundary of) it and it is split; or an edge flip replaces it and its neighbor pipjplp_ip_jp_lpipjpl by pkpiplp_kp_ip_lpkpipl and pkplpjp_kp_lp_jpkplpj .
[The Analysis] Delaunay algorithm: locating prp_rpr visits triangles of the DAG D\mathcal{D}D that were destroyed earlier. To what is each such visit charged, and what total bound results?
To a Delaunay triangle Δ\DeltaΔ destroyed in the same stage whose circumcircle contains prp_rpr . Total point location time: O(n+∑Δcard⁡(K(Δ)))\boldsymbol{O(n + \sum_\Delta \operatorname{card}(K(\Delta)))}O(n+∑Δcard(K(Δ))) . K(Δ)K(\Delta)K(Δ) = the points of PPP in the circumcircle of Δ\DeltaΔ ; the sum is over all Delaunay triangles created. Each Δ\DeltaΔ is charged at most once per point of K(Δ)K(\Delta)K(Δ) .
[The Analysis] In the Delaunay analysis, K(Δ)K(\Delta)K(Δ) is the set of points of PPP in the circumcircle of a triangle Δ\DeltaΔ of DGr\mathcal{DG}_rDGr (the Delaunay triangulation after rrr insertions). What is the intuition for its size?
About O(n/r)O(n/r)O(n/r) , since the first rrr points are a random sample. (Roughly nnn for r=1r = 1r=1 , zero for r=nr = nr=n .) Not true for every triangle, but the sum ∑Δcard⁡(K(Δ))\sum_\Delta \operatorname{card}(K(\Delta))∑Δcard(K(Δ)) behaves as if it were: ∑rO(n/r)=O(nlog⁡n)\sum_r O(n/r) = O(n \log n)∑rO(n/r)=O(nlogn) .
[The Analysis] Lemma 9.13. PPP is in general position, K(Δ)K(\Delta)K(Δ) is the set of points of PPP in the circumcircle of Δ\DeltaΔ . What is ∑Δcard⁡(K(Δ))\sum_\Delta \operatorname{card}(K(\Delta))∑Δcard(K(Δ)) over all Delaunay triangles Δ\DeltaΔ created by the algorithm?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) (expected). The general case is proved with configuration spaces.
[The Analysis] Proof of E[∑Δcard⁡(K(Δ))]=O(nlog⁡n)E[\sum_\Delta \operatorname{card}(K(\Delta))] = O(n \log n)E[∑Δcard(K(Δ))]=O(nlogn) . Tr\mathcal{T}_rTr = triangles of DGr\mathcal{DG}_rDGr ; k(Pr,q)k(P_r, q)k(Pr,q) = number of Δ∈Tr\Delta \in \mathcal{T}_rΔ∈Tr with q∈K(Δ)q \in K(\Delta)q∈K(Δ) ; k(Pr,q,pr)k(P_r, q, p_r)k(Pr,q,pr) = those that are also incident to prp_rpr .Why is E[∑Δ∈Tr∖Tr−1card⁡(K(Δ))]≤3r∑q∈P∖Prk(Pr,q)\displaystyle E\Big[\sum_{\Delta \in \mathcal{T}_r \setminus \mathcal…
Every new triangle is incident to prp_rpr , so the sum equals ∑qk(Pr,q,pr)\sum_q k(P_r, q, p_r)∑qk(Pr,q,pr) ; and a fixed triangle of Tr\mathcal{T}_rTr is incident to the random point pr∈Prp_r \in P_rpr∈Pr with probability at most 3/r3/r3/r . Fix the set PrP_rPr ; only the choice of prp_rpr among its rrr points is random.
[The Analysis] Proof of E[∑Δcard⁡(K(Δ))]=O(nlog⁡n)E[\sum_\Delta \operatorname{card}(K(\Delta))] = O(n \log n)E[∑Δcard(K(Δ))]=O(nlogn) : so far E[∑new Δ at stage rcard⁡(K(Δ))]≤3r∑q∈P∖Prk(Pr,q)E[\sum_{\text{new } \Delta \text{ at stage } r} \operatorname{card}(K(\Delta))] \le \frac{3}{r} \sum_{q \in P \setminus P_r} k(P_r, q)E[∑new Δ at stage rcard(K(Δ))]≤r3∑q∈P∖Prk(Pr,q) , where k(Pr,q)k(P_r, q)k(Pr,q) counts triangles of Tr\mathcal{T}_rTr whose circumcircle contains qqq .How does the pr…
Stage rrr contributes at most 12n−rr12\frac{n-r}{r}12rn−r , and summing over rrr gives O(nlog⁡n)O(n \log n)O(nlogn) . pr+1p_{r+1}pr+1 is a uniform q∈P∖Prq \in P \setminus P_rq∈P∖Pr , so the bound is 3⋅n−rr⋅E[k(Pr,pr+1)]3 \cdot \frac{n-r}{r} \cdot E[k(P_r, p_{r+1})]3⋅rn−r⋅E[k(Pr,pr+1)] . And k(Pr,pr+1)k(P_r, p_{r+1})k(Pr,pr+1) is the number of triangles destroyed by inserting pr+1p_{r+1}pr+1 , which is (created − 2-\,2−2 ), at most 6−26 - 26−2 in expectation. "Destroyed = created −-− 2"…
[A Framework for Randomized Algorithms] Which two steps does every randomized incremental algorithm perform when adding the next object?
Location step: find where the current structure conflicts with the object. Update step: change the structure locally. Examples: linear programming, trapezoidal maps, Delaunay triangulation.
[A Framework for Randomized Algorithms] What is a configuration space (X,Π,D,K)(X, \Pi, D, K)(X,Π,D,K) ?
XXX : a finite set of nnn input objects. Π\PiΠ : the configurations. D(Δ)⊆XD(\Delta) \subseteq XD(Δ)⊆X : the objects defining Δ\DeltaΔ . K(Δ)⊆XK(\Delta) \subseteq XK(Δ)⊆X : the objects in conflict with (killing) Δ\DeltaΔ . card⁡(K(Δ))\operatorname{card}(K(\Delta))card(K(Δ)) is the conflict size of Δ\DeltaΔ . (Unrelated to configuration spaces in motion planning.)
[A Framework for Randomized Algorithms] Which conditions must a configuration space (X,Π,D,K)(X, \Pi, D, K)(X,Π,D,K) satisfy?
d:=max⁡Δcard⁡(D(Δ))d := \max_\Delta \operatorname{card}(D(\Delta))d:=maxΔcard(D(Δ)) is a constant (the maximum degree); the number of configurations with the same defining set is bounded by a constant; and D(Δ)∩K(Δ)=∅D(\Delta) \cap K(\Delta) = \emptysetD(Δ)∩K(Δ)=∅ .
[A Framework for Randomized Algorithms] In a configuration space (X,Π,D,K)(X, \Pi, D, K)(X,Π,D,K) , when is a configuration Δ\DeltaΔ active over S⊆XS \subseteq XS⊆X , and what is T(S)\mathcal{T}(S)T(S) ?
When D(Δ)⊆SD(\Delta) \subseteq SD(Δ)⊆S and K(Δ)∩S=∅K(\Delta) \cap S = \emptysetK(Δ)∩S=∅ . T(S)\mathcal{T}(S)T(S) = the set of configurations active over SSS . The goal of the algorithm is to compute T(X)\mathcal{T}(X)T(X) .
[A Framework for Randomized Algorithms] How is half-plane intersection a configuration space: what are Π\PiΠ , D(Δ)D(\Delta)D(Δ) and K(Δ)K(\Delta)K(Δ) ?
Π\PiΠ : intersection points of the bounding lines; D(Δ)D(\Delta)D(Δ) : the two lines through Δ\DeltaΔ ; K(Δ)K(\Delta)K(Δ) : the half-planes not containing Δ\DeltaΔ . T(S)\mathcal{T}(S)T(S) is the set of vertices of the intersection of the half-planes in SSS .
[A Framework for Randomized Algorithms] How are trapezoidal maps of a set XXX of segments a configuration space?
Π\PiΠ : all trapezoids in the trapezoidal map of any S⊆XS \subseteq XS⊆X ; D(Δ)D(\Delta)D(Δ) : the segments needed to define Δ\DeltaΔ ; K(Δ)K(\Delta)K(Δ) : the segments intersecting Δ\DeltaΔ .
[A Framework for Randomized Algorithms] How is the Delaunay triangulation of a point set XXX in general position a configuration space?
Π\PiΠ : triangles of three non-collinear points; D(Δ)D(\Delta)D(Δ) : its three vertices; K(Δ)K(\Delta)K(Δ) : the points inside its circumcircle. By the empty circle characterization, T(S)\mathcal{T}(S)T(S) is the set of triangles of the Delaunay triangulation of SSS .
[A Framework for Randomized Algorithms] What is the fundamental property of configuration spaces that makes randomized incremental construction of T(Xr)\mathcal{T}(X_r)T(Xr) , Xr={x1,…,xr}X_r = \{x_1, \dots, x_r\}Xr={x1,…,xr} , possible?
Whether Δ∈T(Xr)\Delta \in \mathcal{T}(X_r)Δ∈T(Xr) can be decided locally, from D(Δ)D(\Delta)D(Δ) and K(Δ)K(\Delta)K(Δ) alone, so T(Xr)\mathcal{T}(X_r)T(Xr) does not depend on the order of insertion.
[A Framework for Randomized Algorithms] Theorem 9.14. (X,Π,D,K)(X, \Pi, D, K)(X,Π,D,K) is a configuration space of maximum degree ddd , XrX_rXr the first rrr objects of a random permutation, T(Xr)\mathcal{T}(X_r)T(Xr) the active configurations. Expected number of configurations in T(Xr)∖T(Xr−1)\mathcal{T}(X_r) \setminus \mathcal{T}(X_{r-1})T(Xr)∖T(Xr−1) ?
At most drE[card⁡(T(Xr))]\boldsymbol{\frac{d}{r} E[\operatorname{card}(\mathcal{T}(X_r))]}rdE[card(T(Xr))]
[A Framework for Randomized Algorithms] Theorem 9.14: E[card⁡(T(Xr)∖T(Xr−1))]≤drE[card⁡(T(Xr))]E[\operatorname{card}(\mathcal{T}(X_r) \setminus \mathcal{T}(X_{r-1}))] \le \frac{d}{r} E[\operatorname{card}(\mathcal{T}(X_r))]E[card(T(Xr)∖T(Xr−1))]≤rdE[card(T(Xr))] , with ddd the maximum size of a defining set.How is this proved?
Backwards analysis: fix XrX_rXr and remove a random xrx_rxr . A configuration disappears only if xr∈D(Δ)x_r \in D(\Delta)xr∈D(Δ) , and there are at most d⋅card⁡(T(Xr))d \cdot \operatorname{card}(\mathcal{T}(X_r))d⋅card(T(Xr)) pairs (x,Δ)(x, \Delta)(x,Δ) with x∈D(Δ)x \in D(\Delta)x∈D(Δ) . So in expectation at most drcard⁡(T(Xr))\frac{d}{r} \operatorname{card}(\mathcal{T}(X_r))rdcard(T(Xr)) disappear; then average over all XrX_rXr .
[A Framework for Randomized Algorithms] Theorem 9.15. For a configuration space of maximum degree ddd , bound the expected value of ∑Δcard⁡(K(Δ))\sum_\Delta \operatorname{card}(K(\Delta))∑Δcard(K(Δ)) over all configurations appearing in some T(Xr)\mathcal{T}(X_r)T(Xr) , 1≤r≤n1 \le r \le n1≤r≤n .
∑r=1nd2(n−rr)(E[card⁡(T(Xr))]r)\displaystyle\boldsymbol{\sum_{r=1}^n d^2 \Big(\frac{n-r}{r}\Big) \Big(\frac{E[\operatorname{card}(\mathcal{T}(X_r))]}{r}\Big)}r=1∑nd2(rn−r)(rE[card(T(Xr))]) This bounds the cost of the location steps, as the bound drE[card⁡(T(Xr))]\frac{d}{r} E[\operatorname{card}(\mathcal{T}(X_r))]rdE[card(T(Xr))] on new configurations bounds the structural change.
[A Framework for Randomized Algorithms] Bounding E[∑Δcard⁡(K(Δ))]E[\sum_\Delta \operatorname{card}(K(\Delta))]E[∑Δcard(K(Δ))] in a configuration space of maximum degree ddd : the proof first shows, as for Delaunay triangles, that the configurations new at stage rrr have expected total conflict size ≤dn−rrE[card⁡(T(Xr)∖T(Xr+1))]\le d\frac{n-r}{r} E[\operatorname{card}(\mathcal{T}(X_r) \setminus \mathcal{T}(X_{r+1}))]≤drn−rE[card(T(Xr)∖T(Xr+1))] (those destroyed at stage r+1r + 1r+1 ).Why can…
Destroyed configurations need not be bounded by created ones there. Instead, sum over rrr and charge each configuration to its creation stage. Creation stage i(Δ)≤j(Δ)−1i(\Delta) \le j(\Delta) - 1i(Δ)≤j(Δ)−1 (destruction stage), so n−[j(Δ)−1]j(Δ)−1≤n−i(Δ)i(Δ)\frac{n - [j(\Delta) - 1]}{j(\Delta) - 1} \le \frac{n - i(\Delta)}{i(\Delta)}j(Δ)−1n−[j(Δ)−1]≤i(Δ)n−i(Δ) and the sum is at most ∑rdn−rrE[card⁡(T(Xr)∖T(Xr−1))]\sum_r d \frac{n-r}{r} E[\operatorname{card}(\mathcal{T}(X_r) \setminus \mathcal…
[A Framework for Randomized Algorithms] For points not in general position, which configurations make the Delaunay algorithm fit a configuration space? ( Ω={p0,p−1,p−2}\Omega = \{p_0, p_{-1}, p_{-2}\}Ω={p0,p−1,p−2} , X=P∖{p0}X = P \setminus \{p_0\}X=P∖{p0} .)
Delaunay corners: non-collinear triples (pi,pj,pk)(p_i, p_j, p_k)(pi,pj,pk) , killed by the points inside their circumcircle or on its arc from pip_ipi to pkp_kpk through pjp_jpj . Points from X∪ΩX \cup \OmegaX∪Ω ; D={pi,pj,pk}∩XD = \{p_i, p_j, p_k\} \cap XD={pi,pj,pk}∩X , and KKK counts only points of XXX . Active over SSS iff pi,pj,pkp_i, p_j, p_kpi,pj,pk are consecutive on the boundary of one face of DG(Ω∪S)\mathcal{DG}(\Omega \cup S)DG(Ω∪S) . Triangles as configurations don't wo…
[A Framework for Randomized Algorithms] Delaunay corner: a triple (pi,pj,pk)(p_i, p_j, p_k)(pi,pj,pk) , active iff consecutive on the boundary of a face of the Delaunay graph; KKK contains the points inside its circumcircle.How does the configuration space framework give ∑Δcard⁡(K(Δ))=O(nlog⁡n)\sum_\Delta \operatorname{card}(K(\Delta)) = O(n \log n)∑Δcard(K(Δ))=O(nlogn) for the Delaunay algorithm without general position?
Each new triangle piprpjp_ip_rp_jpiprpj is an active Delaunay corner (pj,pr,pi)(p_j, p_r, p_i)(pj,pr,pi) ; d=3d = 3d=3 and about 6r6r6r corners give at most 54n(ln⁡n+1)54n(\ln n + 1)54n(lnn+1) . By the configuration space bound ∑rd2n−rrE[card⁡(T(Xr))]r\sum_r d^2 \frac{n-r}{r} \frac{E[\operatorname{card}(\mathcal{T}(X_r))]}{r}∑rd2rn−rrE[card(T(Xr))] : ∑r9n−rr⋅6rr≤54n∑r1r\sum_r 9 \frac{n-r}{r} \cdot \frac{6r}{r} \le 54n \sum_r \frac{1}{r}∑r9rn−r⋅r6r≤54n∑rr1 . Worst case for the cor…
[Notes and Comments] Extra vertices added to a triangulation beyond the given points are called Steiner points; triangulating with them allowed is known as meshing.
Triangulations matter in numerical analysis (finite element methods) and computer graphics.
[Notes and Comments] What did Lawson prove about edge flips?
Any two triangulations of a planar point set can be transformed into each other by edge flips.
[Notes and Comments] What did Sibson prove about the angle-vector?
Ignoring degenerate cases, the Delaunay triangulation is the only locally optimal triangulation with respect to the angle-vector.
[Notes and Comments] Why does the Delaunay triangulation suit terrains even though it ignores the heights (the data-independent approach)?
Rippa: it minimizes the roughness of the resulting terrain, whatever the heights are. Roughness: the integral of the square of the L2L_2L2 -norm of the gradient of the terrain. Data-dependent approaches (Dyn et al.) start from the Delaunay triangulation and flip edges to improve height-based criteria.
[Notes and Comments] What is a minimum weight triangulation, and how hard is it to compute?
A triangulation minimizing the sum of its edge lengths. Computing one is NP-complete.