The Straight Skeleton

Imagine a building footprint — a polygon drawn on the ground. Now push every wall inward at the same speed, like a slow flood pressing in from all sides at once. The corners of the polygon must move too, and they trace straight-line paths as the walls advance.

When two walls eventually meet, they annihilate each other and the boundary shrinks further, until the whole polygon has collapsed to a single point (or a few isolated points for complex shapes). The union of all those corner paths is the straight skeleton of the polygon.

The concept was introduced in 1995 by Oswin Aichholzer and Franz Aurenhammer, and it immediately explained something architects had been drawing by hand for centuries: the hip roof. The ridges and valleys of a hip roof that sits over any floor plan are exactly the edges of the straight skeleton of that plan.

Unlike the more common Voronoi diagram (which uses circular wavefronts), the straight skeleton uses straight-edge wavefronts. That single difference produces a simpler, more roof-like result — but it also hides a subtle algorithmic challenge.

Choose a building footprint from the presets below, then press Run to watch the inward wavefront advance step by step. The colored lines that accumulate are the straight skeleton — the ridge and valley lines of the hip roof.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label for="preset-select">{{label_preset}}</label>
  <select id="preset-select">
    <option value="rectangle">{{opt_rectangle}}</option>
    <option value="lshape">{{opt_lshape}}</option>
    <option value="pentagon">{{opt_pentagon}}</option>
    <option value="tshape">{{opt_tshape}}</option>
  </select>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="440" height="310"></canvas>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .85rem; color: #555; }
select { font: 14px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #b0b8c4; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fb; }
.status { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; color: #1d3557; }

// Code not found

Each edge of the skeleton is the bisector of two adjacent walls. When a vertex event occurs (two walls meet and one vanishes), a new bisector starts. The final peak where all remaining walls collapse to a point is the roof's highest ridge. Pause at any moment to measure the slope: every ridge rises at exactly 45° above the floor plan.

The shrinking-polygon picture feels almost too simple. So how hard is it to compute?

• The straight-line bisector idea is clean. Each interior angle contributes a bisector ray. Events happen when two advancing edges collide, and the algorithm just has to process those events in order.
• Reflex vertices complicate everything. When a polygon has a reflex vertex (an inward corner, angle $> 180°$), its bisector ray points outward and can create a split event — a single edge splits into two sub-edges, spawning a new vertex. Split events are harder to predict and handle than simple vertex collapses.
• The naive algorithm is $O(n^2)$. For a polygon with $n$ vertices, a straightforward event-queue approach may process $O(n^2)$ events in the worst case, because each split event can cascade.
• $O(n \log n)$ is achievable. Felkel and Obdrzalek (1998) gave the first practical $O(n \log n)$ algorithm for simple polygons. For polygons with holes or degenerate configurations, the analysis becomes more involved, and robust implementations require careful handling of near-parallel edges and coincident events.
• Open problems remain. No algorithm is known to compute straight skeletons of general (non-simple, multiply-connected) polygons in $o(n^2)$ time in the worst case, and the problem shares DNA with computational geometry challenges where precision arithmetic is critical.

The contrast with the Voronoi diagram is instructive: Voronoi diagrams of point sets are well-solved in $O(n \log n)$, but straight skeletons — despite looking similar — required separate, more recent work to reach the same asymptotic bound.

Once you see the shrinking-polygon idea, you spot it everywhere:

• Architecture — hip roofs: every traditional hip roof over an irregular floor plan has ridges and valleys that follow the straight skeleton exactly. Architects have always drawn them by hand; software now computes them instantly.
• Terrain and map generalisation: shrinking a coastline or a contour polygon inward models how a landmass erodes or a lake grows. The skeleton captures the "axis" of the shape.
• Font and shape offsetting: generating parallel curves around letters and logos — used in engraving, laser cutting and CNC machining — uses the straight skeleton to handle the corners correctly.
• Urban planning: finding the locus of points equidistant from all surrounding streets, or computing setback lines for construction regulations, is a straight-skeleton computation.
• Motion planning: a robot navigating the interior of a polygonal room can use the straight skeleton as a roadmap — the skeleton edges are exactly the paths that keep the robot maximally away from all walls.

Wherever a shape needs to be "shrunk uniformly" or you need the medial axis of a polygon with straight edges (rather than circular arcs), the straight skeleton is the right tool — and its connection to convex-hull thinking makes it a natural topic in computational geometry.

The straight skeleton earns its name: it is the skeleton left behind when a polygon shrinks to nothing, and every bone is a perfectly straight line.

What makes it special is how a single physical intuition — push every wall inward at constant speed — produces a structure rich enough to design roofs, offset fonts, plan robot paths and model coastal erosion. The algorithm is elegant in theory and subtle in practice, with reflex vertices and split events hiding real complexity beneath the clean geometry.

The next time you admire a hip roof or trace a parallel curve around a shape, you are looking at the straight skeleton in action — a structure that lives at the intersection of geometry, architecture and the theory of computational geometry.