Polygon Triangulation, Monotone Decomposition, and Art-Gallery Guards

Polygon Triangulation, Monotone Decomposition, and Art-Gallery Guards

A complicated polygon becomes easier to reason about when we cut it into the simplest possible polygonal pieces: triangles. Triangulation is therefore less about drawing decorative diagonals than about building a certificate of structure. Once a polygon is triangulated, its area is a sum of triangle areas, many dynamic programs have a finite set of separators to explore, and a visibility question can be translated into a statement about a planar graph.

Throughout this part, a simple polygon has one boundary cycle, no self-intersections, and vertices listed counterclockwise. A diagonal joins two nonadjacent vertices and lies in the polygon's closed interior. We first assume exact orientation tests and no three collinear consecutive vertices; later we restore degeneracies and holes.

The Counting Laws: Why the Answer Is Always \(n-2\)

Every triangulation of a simple polygon with \(n\) vertices contains exactly \(n-2\) triangles and \(n-3\) diagonals. These numbers do not depend on the polygon's shape or on which legal diagonals we choose.

One proof grows the triangulation recursively. Any diagonal divides the polygon into polygons with \(a\) and \(b\) vertices, where \(a+b=n+2\) because the two diagonal endpoints belong to both pieces. If the pieces have \(a-2\) and \(b-2\) triangles, together they have \(a+b-4=n-2\). The diagonal count is one less because a tree connecting \(n-2\) triangular regions has \(n-3\) edges. Euler's formula gives the same result globally.

Ears: The Local Route to a Global Triangulation

Three consecutive vertices \((v_{i-1},v_i,v_{i+1})\) form an ear when the segment \(v_{i-1}v_{i+1}\) is a valid diagonal. Equivalently, for a counterclockwise polygon, \(v_i\) is convex and the triangle contains no other polygon vertex. Clipping the ear emits that triangle and removes \(v_i\), leaving a smaller simple polygon.

The two-ears theorem says every simple polygon with at least four vertices has at least two nonoverlapping ears. It supplies both the existence proof for triangulation and a practical baseline algorithm. A naive implementation tests all remaining vertices against every candidate ear and costs \(O(n^2)\). Maintaining candidates in a linked boundary list avoids needless rescanning, though robust spatial indexing is needed to improve the worst-case bound.

EAR-CLIP(P):
  put P's vertices in a circular doubly linked list
  classify each vertex as ear or non-ear
  while more than 3 vertices remain:
    choose an ear v
    output triangle (prev(v), v, next(v))
    delete v
    reclassify only prev(v) and next(v)
  output the final triangle

Ear clipping is attractive because it is small, incremental, and easy to animate. It is also sensitive to nearly collinear corners and to an inconsistent "point in triangle" boundary rule. For guaranteed \(O(n\log n)\) time, a sweep-based monotone decomposition gives a stronger route.

What Makes a Polygon \(y\)-Monotone?

A polygon is \(y\)-monotone if every horizontal line intersects it in an empty set, one point, or one connected segment. Its highest and lowest vertices split the boundary into a left chain and a right chain, each descending in \(y\). This ordering turns a two-dimensional visibility problem into a nearly one-dimensional scan.

At each vertex, inspect whether its two neighbors lie above or below it and whether the interior angle is convex or reflex. With a consistent symbolic tie-break for equal \(y\)-coordinates, the five types are:

Only split and merge vertices obstruct monotonicity. Imagine rain flowing straight downward inside the polygon: at a split vertex, one stream must become two; at a merge vertex, two streams must become one. A diagonal connecting the vertex to a suitable earlier vertex removes that branching.

Sweep Decomposition and the Helper Invariant

Process vertices from highest to lowest. The status structure stores polygon edges crossing the sweep line in left-to-right order. Each status edge \(e\) has a helper: the lowest processed vertex above the sweep line for which a diagonal to \(e\) may still be required. At a split vertex, find the edge immediately to its left, connect to that edge's helper, and make the split vertex the new helper. At a merge vertex, add a diagonal when the old helper is itself a merge vertex, both before removing the incoming edge and while updating the edge to the left.

The invariant is geometric: every unresolved reflex event is represented by exactly the status edge whose interior region can safely receive its diagonal. The tree search costs \(O(\log n)\) per vertex; there are \(n\) events and only \(O(n)\) inserted diagonals. Sorting plus sweeping therefore takes \(O(n\log n)\) time and \(O(n)\) space.

Linear-Time Triangulation of Each Monotone Piece

For one \(y\)-monotone polygon, sort vertices from top to bottom; the chain orders already provide this sequence, so merging them is linear. Keep a stack of processed vertices. If the next vertex lies on the chain opposite the stack top, it sees every stacked vertex: output diagonals to all but the last, clear the stack, and retain the last two vertices. If it lies on the same chain, pop while the diagonal to the newly exposed vertex remains inside the polygon. The orientation inequality reverses between left and right chains.

Each vertex is pushed once and popped once, so triangulating all pieces costs \(O(n)\) after decomposition. The complete pipeline remains \(O(n\log n)\) time and \(O(n)\) space. More sophisticated algorithms triangulate a simple polygon in linear time, but their machinery is rarely the best engineering choice; monotone decomposition offers a clean proof, predictable operations, and reusable sweep infrastructure.

From Triangles to Guards

The art-gallery problem asks how many stationary guards are sufficient to see every point inside a simple polygon. The sharp answer is \(\lfloor n/3\rfloor\), and triangulation makes the bound intuitive.

Triangulate the polygon, then 3-color its vertices so every triangle has one vertex of each color. Such a coloring exists: remove an ear, recursively color the smaller triangulated polygon, then restore the ear tip. Its two neighbors have different colors because they share an edge, so the third color remains available. Equivalently, peel leaves from the triangulation's dual tree.

Every triangle contains a vertex of each color, and every point of the polygon lies in some triangle. Place guards at all vertices of the smallest color class. That class has at most \(\lfloor n/3\rfloor\) vertices, and its guards collectively see every triangle. Some polygons force that many guards, so the bound is not merely sufficient. It is a worst-case theorem, not a claim that every floor plan needs so many: finding the minimum guard set for a particular polygon is much harder.

Holes, Degeneracies, and Representation

Holes break several convenient statements. A polygonal domain with \(h\) holes can be bridged into a weakly simple boundary or triangulated directly in a DCEL. If there are \(n\) total boundary vertices, a triangulation has \(n+2h-2\) triangles and \(n+3h-3\) added edges when bridges are counted. The simple-polygon art-gallery proof does not transfer unchanged: the dual need not be a tree, and visibility around holes is different.

Robust implementations also need explicit policies:

• compare event vertices lexicographically, such as decreasing \((y,-x)\), so horizontal edges have deterministic upper and lower endpoints;
• use exact or filtered orientation predicates for convex/reflex decisions;
• never order sweep-status edges with a rounded intersection coordinate alone;
• decide whether collinear boundary vertices are retained, simplified, or treated as zero-area ears;
• verify every proposed diagonal is topologically inside and does not duplicate an existing half-edge.

A DCEL is especially useful here. Adding a diagonal means splicing two pairs of half-edges and splitting one face into two while preserving twin, next, prev, and incident-face invariants. The overlay labeling from Part 8 can first identify which faces represent the polygon's interior; triangulation then refines only those faces. Geometry decides where an edge may go, while the DCEL records what topology changed.

What to Carry Forward

Triangulation replaces a continuous region with a linear-size set of certified cells. Ears prove that the decomposition always exists; sweep-line helpers make it efficient; monotone stacks finish it in linear time; and 3-coloring turns the same structure into the sharp art-gallery guard bound.

Part 10 changes the question from decomposition to feasibility. Instead of adding diagonals inside one polygon, we will intersect half-planes and optimize over their common region. The recurring lesson is already visible: express a geometric condition through robust sidedness predicates, maintain a compact combinatorial structure, and let that structure carry the proof.