Ch.3: Polygon Triangulation

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 3.1. Guarding and Triangulations 3.2. Partitioning a Polygon into Monotone Pieces 3.3. Triangulating a Monotone Polygon 3.4. Notes and Comments

74 flashcards · Mathematics · by lakesare

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

[Polygon Triangulation] What is the Art Gallery Problem?
How many cameras are needed to guard a given gallery, and where should they be placed? Every part of the gallery must be visible to at least one camera, and there should be as few cameras as possible (fewer screens to watch, lower cost). A gallery floor plan with six cameras.
[Guarding and Triangulations] In the Art Gallery Problem, how are the gallery and a camera modeled?
The gallery is a simple polygon; a camera is a point in the polygon. A floor plan is enough to place the cameras, so the 3-dimensional gallery becomes a polygonal region in the plane.
[Guarding and Triangulations] What is a simple polygon?
A region enclosed by a single closed polygonal chain that does not intersect itself. So in particular a simple polygon has no holes.
[Guarding and Triangulations] Which points of a polygon P\mathcal{P}P does a camera at a point c∈Pc \in \mathcal{P}c∈P see?
The points qqq for which the open segment cq‾\overline{cq}cq lies in the interior of P\mathcal{P}P . Gray: the region seen by one camera.
[Guarding and Triangulations] How many cameras does a convex polygon need?
One, placed anywhere. Every segment between two points of a convex polygon lies in it. So two polygons with the same number nnn of vertices can need very different numbers of cameras, which is why the Art Gallery Theorem gives a worst-case bound in terms of nnn .
[Guarding and Triangulations] How hard is it to compute the minimum number of cameras needed for a given simple polygon?
NP-hard. That is why the chapter settles for a worst-case bound in terms of the number nnn of vertices.
[Guarding and Triangulations] What is a diagonal of a polygon P\mathcal{P}P ?
An open line segment that connects two vertices of P\mathcal{P}P and lies in the interior of P\mathcal{P}P .
[Guarding and Triangulations] What is a triangulation of a polygon?
A decomposition of the polygon into triangles by a maximal set of non-intersecting diagonals. Triangulations are usually not unique.
[Guarding and Triangulations] Why does the definition of a triangulation require the set of non-intersecting diagonals to be maximal?
So that no triangle has a polygon vertex in the interior of one of its edges. This could otherwise happen when the polygon has three consecutive collinear vertices.
[Guarding and Triangulations] Theorem 3.1 Every simple polygon admits a triangulation, and any triangulation of a simple polygon with nnn vertices consists of exactly … ?
n−2\boldsymbol{n - 2}n−2 triangles.
[Guarding and Triangulations] Every simple polygon P\mathcal{P}P with n>3n > 3n>3 vertices has a diagonal.How does the proof find a diagonal?
Leftmost vertex vvv with neighbors u,wu, wu,w : take uw‾\overline{uw}uw if it lies inside P\mathcal{P}P , else vv′‾\overline{vv'}vv′ , v′v'v′ the vertex in triangle uvwuvwuvw farthest from line uwuwuw . If several vertices are leftmost, take the lowest one. uw‾\overline{uw}uw fails when some vertices lie inside triangle uvwuvwuvw or on uw‾\overline{uw}uw . Top: uw‾\overline{uw}uw is a diagonal. Bottom: it is not, and vv′‾\overline{vv'}vv′ is used.
[Guarding and Triangulations] vvv is the leftmost vertex of a simple polygon P\mathcal{P}P , with neighbors uuu and www , and uw‾\overline{uw}uw is not a diagonal. v′v'v′ is the vertex inside triangle uvwuvwuvw (or on uw‾\overline{uw}uw ) farthest from the line through uuu and www .Why is vv′‾\overline{vv'}vv′ a diagonal?
An edge of P\mathcal{P}P crossing vv′‾\overline{vv'}vv′ would have an endpoint inside the triangle farther from line uwuwuw than v′v'v′ , contradicting the choice of v′v'v′ .
[Guarding and Triangulations] In the proof that a triangulation of a simple polygon P\mathcal{P}P with nnn vertices has n−2n - 2n−2 triangles: a diagonal cuts P\mathcal{P}P into subpolygons with m1m_1m1 and m2m_2m2 vertices. What is m1+m2m_1 + m_2m1+m2 , and how does the induction finish?
m1+m2=n+2\boldsymbol{m_1 + m_2 = n + 2}m1+m2=n+2 , so there are (m1−2)+(m2−2)=n−2(m_1 - 2) + (m_2 - 2) = n - 2(m1−2)+(m2−2)=n−2 triangles. The two endpoints of the diagonal occur in both subpolygons; every other vertex in exactly one. By induction each subpolygon with mim_imi vertices has mi−2m_i - 2mi−2 triangles.
[Guarding and Triangulations] A triangulation of a simple polygon with nnn vertices has n−2n - 2n−2 triangles. How many diagonals does it have?
n−3\boldsymbol{n - 3}n−3 Count triangle sides: 3(n−2)=n+2d3(n - 2) = n + 2d3(n−2)=n+2d , since each of the nnn polygon edges is a side of one triangle and each of the ddd diagonals a side of two. So d=n−3d = n - 3d=n−3 .
[Guarding and Triangulations] A simple polygon with nnn vertices is triangulated. Why do n−2n - 2n−2 cameras suffice to guard it, and why would cameras on diagonals do better?
One camera per triangle; a camera on a diagonal sees both triangles beside that diagonal, which suggests roughly n/2n/2n/2 cameras. Cameras at vertices are better still: a vertex can be incident to many triangles, and a camera there sees all of them.
[Guarding and Triangulations] What is a 3-coloring of a triangulated polygon?
A coloring of the vertices with three colors such that any two vertices connected by an edge or a diagonal have different colors. Every triangle then has one vertex of each color.
[Guarding and Triangulations] A triangulated simple polygon P\mathcal{P}P with nnn vertices has a 3-coloring (colors white, gray, black).How does this give a set of at most ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ cameras guarding P\mathcal{P}P ?
Place cameras at the vertices of the smallest color class. Every triangle has a vertex of each color, so any one color class guards all triangles. The three classes have nnn vertices in total, so the smallest has at most ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ .
[Guarding and Triangulations] What is the dual graph G(TP)\mathcal{G}(\mathcal{T}_\mathcal{P})G(TP) of a triangulation TP\mathcal{T}_\mathcal{P}TP of a polygon P\mathcal{P}P ?
A node for every triangle, and an arc between two nodes whose triangles share a diagonal. The arcs correspond to the diagonals of TP\mathcal{T}_\mathcal{P}TP .
[Guarding and Triangulations] Why is the dual graph of a triangulation of a simple polygon a tree?
Every diagonal cuts the polygon into two, so removing any arc disconnects the dual graph. This fails for polygons with holes: a diagonal there need not disconnect the polygon.
[Guarding and Triangulations] The dual graph of a triangulated simple polygon (a node per triangle, an arc per shared diagonal) is a tree.How does a depth-first search on the dual graph compute a 3-coloring?
Color the first triangle with all three colors; each newly reached triangle has one uncolored vertex: give it the color missing on the shared diagonal. Because the dual graph is a tree, the other neighbors of ν\nuν are not yet visited, so this color never conflicts. Invariant: all vertices of visited triangles are colored, with no two connected vertices alike.
[Guarding and Triangulations] Which polygon shows that some simple polygons with nnn vertices need ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ cameras?
A comb with ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ prongs, built so that no point sees into two prongs. Each prong has two edges; the prongs are joined by horizontal edges above a long horizontal base edge.
[Guarding and Triangulations] Art Gallery Theorem (Theorem 3.2) For a simple polygon with nnn vertices, how many cameras are occasionally necessary and always sufficient to see every point of the polygon?
⌊n/3⌋\boldsymbol{\lfloor n/3 \rfloor}⌊n/3⌋ Sufficient: 3-color a triangulation, take the smallest color class. Necessary: the comb with ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ prongs.
[Guarding and Triangulations] A simple polygon gallery has 20 vertices. How many cameras always suffice, and can fewer always be enough?
6 suffice; no, some 20-vertex polygons need 6. ⌊20/3⌋=6\lfloor 20/3 \rfloor = 6⌊20/3⌋=6 by the Art Gallery Theorem.
[Guarding and Triangulations] Theorem 3.3 Let P\mathcal{P}P be a simple polygon with nnn vertices. In what time can a set of ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ camera positions be computed such that every point of P\mathcal{P}P is visible from one of them?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) Triangulate in O(nlog⁡n)O(n \log n)O(nlogn) , stored as a DCEL so one can step between neighboring triangles in O(1)O(1)O(1) . Then the DFS 3-coloring and choosing the smallest color class take linear time.
[Partitioning a Polygon into Monotone Pieces] The proof that every simple polygon has a triangulation finds a diagonal in linear time (via the leftmost vertex) and recurses on the two subpolygons.What is the worst-case running time of this algorithm, and why?
O(n2)\boldsymbol{O(n^2)}O(n2) : the diagonal may split off just a triangle, leaving a polygon with n−1n - 1n−1 vertices. This always happens when the diagonal uw‾\overline{uw}uw between the leftmost vertex's neighbors works.
[Partitioning a Polygon into Monotone Pieces] How can a convex polygon with nnn vertices be triangulated, and how fast?
Draw diagonals from one vertex to all other vertices except its neighbors: O(n)O(n)O(n) time.
[Partitioning a Polygon into Monotone Pieces] Why does the chapter triangulate a simple polygon via monotone pieces rather than via convex pieces?
Partitioning a polygon into convex pieces is as difficult as triangulating it; partitioning into monotone pieces is a lot easier.
[Partitioning a Polygon into Monotone Pieces] When is a simple polygon monotone with respect to a line ℓ\ellℓ ?
Every line ℓ′\ell'ℓ′ perpendicular to ℓ\ellℓ intersects the polygon in a connected set: a segment, a point, or nothing. A yyy -monotone polygon: every horizontal line meets it in one segment.
[Partitioning a Polygon into Monotone Pieces] What characteristic walking property does a yyy -monotone polygon have?
Walking from a topmost to a bottommost vertex along the left (or the right) boundary chain, you always move down or horizontally, never up.
[Partitioning a Polygon into Monotone Pieces] What is a turn vertex of a polygon?
A vertex where the walking direction switches between downward and upward, walking from the topmost to the bottommost vertex along a boundary chain. To partition into yyy -monotone pieces, the turn vertices must be removed by adding diagonals.
[Partitioning a Polygon into Monotone Pieces] At a turn vertex vvv , both incident edges go down and the polygon's interior lies locally above vvv . Which diagonal removes vvv as a turn vertex, and why?
A diagonal going up from vvv . vvv then lies in both pieces, and in each it has an edge going down (an original edge) and one going up (the diagonal).
[Partitioning a Polygon into Monotone Pieces] To handle vertices with equal yyy -coordinate, when is a point ppp below a point qqq ?
py<qy\boldsymbol{p_y < q_y}py<qy , or py=qyp_y = q_ypy=qy and px>qxp_x > q_xpx>qx . Above is the reverse: py>qyp_y > q_ypy>qy , or py=qyp_y = q_ypy=qy and px<qxp_x < q_xpx<qx . This is the ordinary above/below in the plane rotated slightly clockwise, where no two points have equal yyy -coordinate.
[Partitioning a Polygon into Monotone Pieces] Define the five vertex types of a polygon: start, split, end, merge, regular (using "above"/"below" with ties broken by xxx ).
Both neighbors below: start (interior angle <π< \pi<π ) or split ( >π> \pi>π ). Both above: end ( <π< \pi<π ) or merge ( >π> \pi>π ). Otherwise regular. A regular vertex has one neighbor above and one below. The four others are the turn vertices.
[Partitioning a Polygon into Monotone Pieces] Why are the polygon vertex types called split and merge vertices?
When a downward sweep line reaches a split vertex, a component of its intersection with the polygon splits; at a merge vertex, two components merge.
[Partitioning a Polygon into Monotone Pieces] Lemma 3.4 A polygon is yyy -monotone if … ?
It has no split vertices and no merge vertices.
[Partitioning a Polygon into Monotone Pieces] P\mathcal{P}P is not yyy -monotone, so a horizontal line ℓ\ellℓ meets it in several components; the leftmost one is a segment pq‾\overline{pq}pq . Follow the boundary from qqq upward (interior on the left) until it meets ℓ\ellℓ again, at rrr .If r≠pr \neq pr=p , which vertex does the proof that P\mathcal{P}P has a split or merge vertex use?
The highest vertex between qqq and rrr is a split vertex. (a): r≠pr \neq pr=p . (b): r=pr = pr=p .
[Partitioning a Polygon into Monotone Pieces] P\mathcal{P}P is not yyy -monotone, so a horizontal line ℓ\ellℓ meets it in several components; the leftmost one is a segment pq‾\overline{pq}pq . Following the boundary from qqq upward, it meets ℓ\ellℓ again exactly at ppp .How does the proof then find a merge vertex?
Follow the boundary from qqq in the other direction to the next intersection r′r'r′ with ℓ\ellℓ ; the lowest vertex between qqq and r′r'r′ is a merge vertex. r′≠pr' \neq pr′=p : otherwise the boundary would meet ℓ\ellℓ only twice, and ℓ\ellℓ would meet P\mathcal{P}P in one component.
[Partitioning a Polygon into Monotone Pieces] How does the algorithm MakeMonotone remove the split and merge vertices of a simple polygon?
A diagonal going upward from each split vertex and a diagonal going downward from each merge vertex, all non-intersecting. With no split or merge vertices left, every piece is yyy -monotone.
[Partitioning a Polygon into Monotone Pieces] In MakeMonotone's downward plane sweep over a simple polygon, what are the event points, and how is the next event found?
The polygon's vertices, in a priority queue on yyy -coordinate (leftmost first on ties), giving the next event in O(log⁡n)O(\log n)O(logn) . No new events arise during the sweep, so sorting the vertices beforehand and using the sorted list gives the next event in O(1)O(1)O(1) .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P . At a split vertex viv_ivi , eje_jej is the edge immediately left of viv_ivi on the sweep line and eke_kek the edge immediately right.What is the helper of eje_jej ?
The lowest vertex above the sweep line whose horizontal segment to eje_jej lies inside P\mathcal{P}P . Equivalently, the lowest vertex between eje_jej and eke_kek above viv_ivi , or, if none, the upper endpoint of eje_jej or of eke_kek . It can be the upper endpoint of eje_jej itself.
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
To helper(ej)\mathit{helper}(e_j)helper(ej) , the helper of the edge eje_jej immediately left of viv_ivi . This vertex lies above viv_ivi , and the diagonal to it crosses no edge.
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
viv_ivi becomes the helper of the edge eje_jej left of it; the vertex vmv_mvm that later replaces viv_ivi as helper of eje_jej is the one to connect to. vmv_mvm is the highest vertex below the sweep line between eje_jej and the edge right of viv_ivi (a split vertex upside down). If the helper is never replaced, connect viv_ivi to the lower endpoint of eje_jej .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
The algorithm only ever queries the edge directly left of a split, merge or regular vertex, and such an edge has the interior to its right. The leaves of T\mathcal{T}T are in the left-to-right order of the edges along the sweep line.
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
Whether the old helper is a merge vertex; if so, add the diagonal between the old helper and the new one. At a split vertex a diagonal is always added. If the old helper was a merge vertex, one diagonal removes both a split and a merge vertex.
[Partitioning a Polygon into Monotone Pieces] How does MakeMonotone add a diagonal to the DCEL D\mathcal{D}D of the polygon in O(1)O(1)O(1) time?
Cross-pointers between the edges in the status structure and the corresponding edges in D\mathcal{D}D , then some simple pointer changes. If the polygon is given otherwise, e.g. as a counterclockwise vertex list, a DCEL is built first.
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
Insert eie_iei in T\mathcal{T}T and set helper(ei)←vi\mathit{helper}(e_i) \leftarrow v_ihelper(ei)←vi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
If helper(ei−1)\mathit{helper}(e_{i-1})helper(ei−1) is a merge vertex, add the diagonal from viv_ivi to it. Delete ei−1e_{i-1}ei−1 from T\mathcal{T}T .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
Find eje_jej directly left of viv_ivi in T\mathcal{T}T ; add the diagonal viv_ivi to helper(ej)\mathit{helper}(e_j)helper(ej) ; set helper(ej)←vi\mathit{helper}(e_j) \leftarrow v_ihelper(ej)←vi ; insert eie_iei with helper viv_ivi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
(1) Diagonal to helper(ei−1)\mathit{helper}(e_{i-1})helper(ei−1) if it is a merge vertex; delete ei−1e_{i-1}ei−1 . (2) For eje_jej directly left of viv_ivi : diagonal to helper(ej)\mathit{helper}(e_j)helper(ej) if merge; helper(ej)←vi\mathit{helper}(e_j) \leftarrow v_ihelper(ej)←vi . Step (1) is exactly what an end vertex does. In step (2), viv_ivi becomes the helper of eje_jej , so the vertex that later replaces it gets the diagonal from viv_ivi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
Replace ei−1e_{i-1}ei−1 by eie_iei in T\mathcal{T}T : diagonal to helper(ei−1)\mathit{helper}(e_{i-1})helper(ei−1) if it is a merge vertex, delete ei−1e_{i-1}ei−1 , insert eie_iei with helper viv_ivi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
Find eje_jej directly left of viv_ivi ; if helper(ej)\mathit{helper}(e_j)helper(ej) is a merge vertex, add the diagonal to it; set helper(ej)←vi\mathit{helper}(e_j) \leftarrow v_ihelper(ej)←vi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps a horizontal line downward over a simple polygon P\mathcal{P}P with vertices v1,…,vnv_1, \dots, v_nv1,…,vn in counterclockwise order and edges ei=vivi+1‾e_i = \overline{v_iv_{i+1}}ei=vivi+1 . The status T\mathcal{T}T is a balanced search tree of the edges crossing the sweep line that have the interior of P\mathcal{P}P to their right, each stored with its helper (the lowest vertex above the sweep line whose horizontal segmen…
The diagonal v8v2‾\overline{v_8v_2}v8v2 is added, and e7e_7e7 is deleted from T\mathcal{T}T . All diagonals of the example. Others: split vertex v14v_{14}v14 to helper(e9)=v8\mathit{helper}(e_9) = v_8helper(e9)=v8 ; regular vertex v6v_6v6 to merge vertex v4v_4v4 .
[Partitioning a Polygon into Monotone Pieces] Lemma 3.5 What does the algorithm MakeMonotone add to a simple polygon P\mathcal{P}P ?
A set of non-intersecting diagonals that partitions P\mathcal{P}P into monotone subpolygons. The pieces have no split or merge vertices, so they are monotone; it remains to show the segments are valid, non-crossing diagonals.
[Partitioning a Polygon into Monotone Pieces] MakeMonotone adds the segment vmvi‾\overline{v_mv_i}vmvi at split vertex viv_ivi , where vm=helper(ej)v_m = \mathit{helper}(e_j)vm=helper(ej) and eje_jej , eke_kek are the edges directly left and right of viv_ivi . QQQ is the quadrilateral bounded by the horizontal lines through vmv_mvm and viv_ivi and by eje_jej and eke_kek .Why does no polygon edge cross vmvi‾\overline{v_mv_i}vmvi ?
QQQ contains no vertex, so a crossing edge would have to cross a horizontal segment from vmv_mvm or viv_ivi to eje_jej . QQQ is empty, else vmv_mvm would not be the helper of eje_jej . And no edge crosses those horizontal segments, because eje_jej lies directly left of both vmv_mvm and viv_ivi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone adds the segment vmvi‾\overline{v_mv_i}vmvi at split vertex viv_ivi , where vm=helper(ej)v_m = \mathit{helper}(e_j)vm=helper(ej) and eje_jej , eke_kek are the edges directly left and right of viv_ivi . QQQ is the quadrilateral bounded by the horizontal lines through vmv_mvm and viv_ivi and by eje_jej and eke_kek ; it contains no vertex.Why does no previously added diagonal cross vmvi‾\overline{v_mv_i}vmvi ?
A previously added diagonal has both endpoints above viv_ivi and none inside QQQ , so it cannot cross vmvi‾\overline{v_mv_i}vmvi .
[Partitioning a Polygon into Monotone Pieces] MakeMonotone sweeps over the nnn vertices of a simple polygon with a priority queue Q\mathcal{Q}Q , a balanced search tree T\mathcal{T}T of edges and a DCEL D\mathcal{D}D .What does one event cost, and why?
O(log⁡n)\boldsymbol{O(\log n)}O(logn) : one operation on Q\mathcal{Q}Q , at most one query, one insertion and one deletion on T\mathcal{T}T , and at most two O(1)O(1)O(1) diagonal insertions into D\mathcal{D}D . Building Q\mathcal{Q}Q takes O(n)O(n)O(n) , initializing T\mathcal{T}T O(1)O(1)O(1) .
[Partitioning a Polygon into Monotone Pieces] Theorem 3.6 A simple polygon with nnn vertices can be partitioned into yyy -monotone polygons in what time and storage?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage. Storage: every vertex is stored at most once in the event queue, every edge at most once in the status tree.
[Triangulating a Monotone Polygon] When is a polygon strictly yyy -monotone?
It is yyy -monotone and has no horizontal edges. Then walking from the highest to the lowest vertex along either boundary chain always goes strictly down.
[Triangulating a Monotone Polygon] What is the key idea of triangulating a strictly yyy -monotone polygon?
Greedy: handle vertices top to bottom on both chains, adding diagonals whenever possible. Vertices with equal yyy -coordinate: the leftmost first.
[Triangulating a Monotone Polygon] TriangulateMonotonePolygon handles the vertices of a strictly yyy -monotone polygon top to bottom, using a stack S\mathcal{S}S of handled vertices that may still need diagonals.What shape does the untriangulated part above the last handled vertex have (the invariant)?
An upside-down funnel: one side is part of a single edge, the other a chain of reflex vertices, which are on the stack. Only the highest stack vertex (at the bottom of the stack) is convex; the lowest, last encountered, is on top. Reflex: interior angle at least 180∘180^\circ180∘ .
[Triangulating a Monotone Polygon] TriangulateMonotonePolygon handles the vertices of a strictly yyy -monotone polygon P\mathcal{P}P from top to bottom. A stack S\mathcal{S}S holds the handled vertices that may still need diagonals. Invariant: the untriangulated part above the last handled vertex is an upside-down funnel, bounded by part of a single edge on one side and a chain of reflex vertices on the other (the stack, with the highest, convex vertex at the bottom).The next vertex uju_juj li…
Pop all stack vertices and add diagonals from uju_juj to all but the last popped one; then push the old top of the stack and uju_juj . The last (bottom) one is the upper endpoint of the single funnel edge, already joined to uju_juj .
[Triangulating a Monotone Polygon] TriangulateMonotonePolygon handles the vertices of a strictly yyy -monotone polygon P\mathcal{P}P from top to bottom. A stack S\mathcal{S}S holds the handled vertices that may still need diagonals. Invariant: the untriangulated part above the last handled vertex is an upside-down funnel, bounded by part of a single edge on one side and a chain of reflex vertices on the other (the stack, with the highest, convex vertex at the bottom).The next vertex uju_juj li…
Pop one vertex (joined to uju_juj by an edge), then pop and connect to uju_juj while the diagonal lies inside; push back the last popped vertex, then push uju_juj . The connectable vertices are consecutive on top of the stack. Whether uju_juj connects to vkv_kvk depends only on uju_juj , vkv_kvk and the previously popped vertex. Left: some diagonals added. Right: none, the boundary neighbor of uju_juj is pushed back.
[Triangulating a Monotone Polygon] TriangulateMonotonePolygon merges the left and right chains of a strictly yyy -monotone polygon into u1,…,unu_1, \dots, u_nu1,…,un by decreasing yyy , pushes u1,u2u_1, u_2u1,u2 onto a stack, and handles u3,…,un−1u_3, \dots, u_{n-1}u3,…,un−1 in a loop.What is done with the lowest vertex unu_nun ?
Add diagonals from unu_nun to all stack vertices except the first and the last one.
[Triangulating a Monotone Polygon] TriangulateMonotonePolygon merges the chains of a strictly yyy -monotone polygon with nnn vertices by yyy in O(n)O(n)O(n) , then runs a loop for j=3,…,n−1j = 3, \dots, n - 1j=3,…,n−1 that pops and pushes stack vertices.Why is the loop O(n)O(n)O(n) in total, although one iteration can take linear time?
Each iteration pushes at most two vertices, so there are at most 2n−42n - 42n−4 pushes in total (counting the initial two), and pops cannot exceed pushes.
[Triangulating a Monotone Polygon] Theorem 3.7 In what time can a strictly yyy -monotone polygon with nnn vertices be triangulated?
O(n)\boldsymbol{O(n)}O(n) (linear). The stack algorithm is similar to the convex hull algorithm of Chapter 1.
[Triangulating a Monotone Polygon] The monotone pieces from MakeMonotone may have horizontal edges, but the monotone triangulation algorithm needs strictly yyy -monotone polygons. Why does combining them still work?
Both treat equal- yyy vertices from left to right, which amounts to a slight clockwise rotation of the plane; in it, the pieces are strictly monotone.
[Triangulating a Monotone Polygon] Theorem 3.8 A simple polygon with nnn vertices can be triangulated in what time and storage?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage. O(nlog⁡n)O(n \log n)O(nlogn) to partition into monotone pieces, then O(n)O(n)O(n) to triangulate them all, since their vertex counts sum to O(n)O(n)O(n) .
[Triangulating a Monotone Polygon] Can the monotone-pieces algorithm also triangulate polygons with holes?
Yes. Splitting into monotone pieces nowhere used that the polygon is simple.
[Triangulating a Monotone Polygon] What does it mean to triangulate a planar subdivision S\mathcal{S}S ?
Partition a bounding box BBB of S\mathcal{S}S into triangles by a maximal set of non-intersecting diagonals. BBB contains all edges of S\mathcal{S}S in its interior; a diagonal here is a segment between vertices of S\mathcal{S}S or BBB that crosses no edge of S\mathcal{S}S . Bold: edges of S\mathcal{S}S and BBB . Dashed: diagonals.
[Triangulating a Monotone Polygon] Theorem 3.9 A planar subdivision with nnn vertices in total can be triangulated in what time and storage?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) time, O(n)\boldsymbol{O(n)}O(n) storage. Split the subdivision into monotone pieces, then triangulate the pieces.
[Notes and Comments] Who posed the Art Gallery Problem, who first proved the ⌊n/3⌋\lfloor n/3 \rfloor⌊n/3⌋ bound, and who found the simple 3-coloring proof?
Posed by Klee (1973, to Chvátal); first proved by Chvátal (1975); simple proof by Fisk. Fisk's proof is based on Meisters' Two Ears Theorem. The result is also called the Watchman Theorem.
[Notes and Comments] Which lower bound holds for triangulating subdivisions with holes?
Ω(nlog⁡n)\boldsymbol{\Omega(n \log n)}Ω(nlogn) For simple polygons, whether o(nlog⁡n)o(n \log n)o(nlogn) is possible was a long-standing open problem.
[Notes and Comments] What are the milestones below O(nlog⁡n)O(n \log n)O(nlogn) for triangulating a simple polygon?
O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn) (Tarjan and Van Wyk, 1988); O(nlog⁡∗n)O(n \log^* n)O(nlog∗n) randomized (Clarkson et al., Devillers, Seidel); O(n)O(n)O(n) deterministic (Chazelle, 1990). log⁡∗n\log^* nlog∗n : how often you can take the logarithm before the result is below 1. A randomized linear algorithm came later (Amato et al.).
[Notes and Comments] What is a tetrahedralization of a polytope, and does one always exist?
A decomposition into non-overlapping tetrahedra whose vertices are vertices of the polytope. No, not always without extra vertices. For a simple polytope with nnn vertices, Θ(n2)\Theta(n^2)Θ(n2) extra vertices may be needed and always suffice (Chazelle). Deciding whether none are needed is NP-complete.