Polygon Triangulation(slides partially by Daniel Vlasic )Triangulation: Definition• Triangulation of a simple polygon P: decomposition of P into triangles by a maximal set of non-intersecting diagonals• Diagonal: an open line segment that connects two vertices of P and lies in the interior of P• Triangulations are usually not uniqueMotivation: Guarding an Art Gallery• An art gallery has several rooms • Each room guarded by cameras that see in all directions• Want to have few cameras that cover the whole galleryTriangulation: Existence• Theorem:– Every simple polygon admits a triangulation– Any triangulation of a simple polygon with n vertices consists of exactly n-2 triangles• Proof: – Base case: n=3• 1 triangle (=n-2) • trivially correct – Inductive step: assume theorem holds for all m<nInductive step• First, prove existence of a diagonal: – Let v be the leftmost vertex of P– Let u and w be the two neighboring vertices of v– If open segment uwlies inside P, then uwis a diagonalInductive step ctd.• If open segment uw does not lie inside P– there are one or more vertices inside triangle uvw– of those vertices, let v' be the farthest one from uw– segment vv' cannot intersect any edge of P, so vv' is a diagonal • Thus, a diagonal exists • Can recurse on both sides• Math works outBack to cameras• Where should we put the cameras ?• Idea: cover every triangle– 3-color the nodes (for each edge, endpoints have different colors)– Each triangle has vertices with all 3 colors– Can choose the least frequent color class n/3 cameras suffice– There are polygons that require n/3cameras3-coloring Always Possible• Take the dual graph G• This graph has no cycles• Find 3-coloring by DFS traversal of G:– Start from any triangle and 3-color its vertices– When reaching new triangle we cross an already colored diagonal – Choose the third color to finish the triangleHow to triangulate fast• Partition the polygon into y-monotone parts, i.e., into polygons P such that an intersection of any horizontal line L with P is connected• Triangulate the monotone partsMonotone partitioning• Line sweep (top down)• Vertices where the direction changes downward<>upward are called turn vertices• To have y-monotone pieces, we need to get rid of turn vertices:– when we encounter a turn vertex, it might be necessary to introduce a diagonal and split the polygon into pieces– we will not add diagonals at all turn verticesVertex OntologyAdding diagonals• To partition P into y-monotone pieces, get rid of split and merge vertices – add a diagonal going upward from each split vertex – add a diagonal going downward from each merge vertex• Where do the edges go ?Helpers• Let helper(ej) be the lowest vertex above the sweep-line such that the horizontal segment connecting the vertex toejlies inside PRemoving Split Vertices• For a split vertex vi, let ejbe the edge immediately to the left of it • Add a diagonal from vito helper(ej)Removing Merge Vertices• For a merge vertex vi, let ejbe the edge immediately to the left of it • vibecomes helper(ej) once we reach it • Whenever the helper(ej) is replaced by some vertex vm, add a diagonal from vmto vi• If viis never replaced as helper(ej) , we can connect it to the lower endpoint of ejThe algorithm• Use plane sweep method – move sweep line downward over the plane (need to sort first)– halt the line on every vertex – handle the event depending on the vertex type – events: • edge starts (insert into a BST) • edge ends (add a diagonal if the helper is a merge vertex, remove from BST) • edge changes a helper (add a diagonal if old helper was a merge vertex) • new vertex is a split vertex (must add a diagonal) • Time: O(n log n)Triangulating monotone polygonAltogether• Can triangulate a polygon in O(n log n)time• Fairly simple O(n log*n) time algorithms• Very complex O(n) time