Monotone Polygon Triangulation

Give a computer graphics engine, a mesh generator, or a robot's path planner a simple polygon — any closed shape with straight sides and no self-crossings — and sooner or later it needs to break that polygon into triangles. Triangles are the atoms of computational geometry: easy to render, easy to reason about, easy to feed into physics and rendering pipelines.

Any simple polygon with $n$ vertices can always be triangulated into exactly $n-2$ triangles using only diagonals that stay inside the shape. The question is not whether it can be done — it's how fast.

The naive approach pokes around for a valid diagonal, cuts, and repeats, costing $O(n^2)$ or worse. But if you first slice the polygon into pieces that are y-monotone — pieces where a vertical sweep never has to backtrack — each piece can be triangulated in a single linear pass with nothing more than a stack. That two-stage idea, sweep-to-split then stack-to-triangulate, is one of the cleanest results in computational geometry.

Below is a y-monotone polygon: a horizontal line crosses its boundary at most twice at any height, so every vertex can be visited in order from top to bottom. Press Step to advance the sweep one vertex at a time and watch the stack fill up and empty out as diagonals get added.

<p class="hint">{{hint_para}}</p>
<svg id="stage" viewBox="0 0 320 320" class="stage"></svg>
<div class="panel">
  <div class="stackbox">
    <div class="stacklabel">{{stack_label}}</div>
    <div id="stackview" class="stackview"></div>
  </div>
  <div class="status" id="status">{{status_ready}}</div>
</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.stage { width: 100%; max-width: 320px; height: 260px; display: block; margin: 0 auto; background: #f7f9fb;
         border: 1px solid #dde3e9; border-radius: 8px; }
.poly-fill { fill: #e8eef3; stroke: none; }
.edge { fill: none; stroke: #1d3557; stroke-width: 2; }
.diagonal { fill: none; stroke: #e63946; stroke-width: 2; stroke-dasharray: 5 4; }
.vtx { fill: #1d3557; }
.vtx.done { fill: #adb1b8; }
.vtx.current { fill: #e63946; }
.panel { display: flex; align-items: flex-start; justify-content: space-between; gap: .75rem;
         margin: .6rem 0; flex-wrap: wrap; }
.stackbox { background: #fff; border: 1px solid #dde3e9; border-radius: 8px; padding: .4rem .6rem; min-width: 110px; }
.stacklabel { font-size: .75rem; font-weight: 700; color: #1d3557; text-transform: uppercase; letter-spacing: .03em; margin-bottom: .3rem; }
.stackview { display: flex; flex-direction: column-reverse; gap: 3px; min-height: 1.4em; }
.stackitem { font: 700 13px ui-monospace, monospace; background: #e8eef3; color: #1d3557; border-radius: 5px;
             padding: .1rem .4rem; text-align: center; }
.status { font-size: .95rem; font-weight: 600; flex: 1; min-width: 160px; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Each step does one of two cheap things: push a vertex onto the stack, or pop vertices off it while drawing diagonals, testing only whether a turn is convex. There is no searching for "the next valid cut" — the stack always tells you exactly which diagonal is safe to draw next. That is why the whole pass costs O(n): every vertex is pushed once and popped once.

The complexity story here comes in two very different halves.

• Triangulating a y-monotone polygon is $O(n)$. Sweep the $n$ vertices top to bottom, keeping a stack of vertices that still need diagonals. At each step you either push the current vertex or pop a chain of vertices while drawing a diagonal to each — every vertex is pushed and popped exactly once, so the total work is linear (Garey, Johnson, Preparata & Tarjan, 1978).
• Splitting an arbitrary simple polygon into y-monotone pieces is $O(n \log n)$. A sweep line finds "merge" and "split" vertices — the places where the boundary folds back on itself — and connects each one to a partner below or above it with a diagonal, using a balanced search structure to find that partner quickly.
• Putting both phases together still costs $O(n \log n)$, dominated by the splitting phase — and for decades this was believed to be unavoidable, on par with the $\Omega(n \log n)$ lower bound for comparison-based sorting.
• Bernard Chazelle broke that ceiling in 1991, showing that any simple polygon can be triangulated in $O(n)$ time using a far more intricate scheme built on hierarchical partitioning ideas that echo the divide-and-conquer style behind algorithms like Closest Pair of Points — a landmark result, though the constant hidden in the big-O is large enough that the $O(n \log n)$ sweep is what most real systems actually run.

So the monotone case is not a toy simplification — it is the linear-time core that the general algorithm is built around, whether you stop at $O(n \log n)$ or push all the way to Chazelle's optimal $O(n)$.

Turning a polygon into triangles is one of the most quietly ubiquitous operations in applied computing:

• Computer graphics: GPUs only know how to rasterize triangles, so every polygon drawn on screen — from a font glyph to a game character's silhouette — gets triangulated first.
• Finite-element analysis: engineers simulating stress, heat, or airflow break a 2D domain into a triangular mesh, then solve equations on each small piece.
• Geographic information systems: maps represent countries, lakes, and parcels as polygons; triangulating them enables area computation, terrain modeling, and fast point-in-region queries.
• Robotics and games: navigation meshes for pathfinding and collision-detection routines both rely on decomposing complex shapes into simple triangular cells.

Any time software needs to reason about an irregular 2D shape numerically, triangulation is usually the first translation step — turning geometry into algebra it can compute with.

A polygon triangulation problem that looks like it should require constant backtracking turns out to have a beautifully local solution: sweep from top to bottom, keep a stack of unresolved vertices, and let convexity tests tell you exactly when to cut a diagonal. That is enough to triangulate any y-monotone shape in $O(n)$, and with an $O(n \log n)$ splitting step it handles any simple polygon at all.

The lesson generalizes well beyond geometry: many hard-looking problems become easy once you find the right decomposition — much like how a well-chosen structure sets a hard floor on comparison sorting, or how Longest Common Subsequence falls to the right subproblem split.