The Medial Axis

Imagine a field of dry grass shaped like a capital letter H. You light the entire boundary at once. The fire races inward from every edge at the same speed. Where two flame-fronts collide they cannot advance further — they stop and leave a faint charred line. That charred line is the medial axis: the skeleton of the shape.

The idea was formalised in 1967 by the biologist Harry Blum, who was looking for a compact way to describe biological shapes. His insight was elegant: instead of cataloguing every point on a boundary, describe a shape by the centers of all the largest disks that fit inside it without crossing the boundary. Each such center is a point on the medial axis, and the radius of its disk is the thickness of the shape at that point.

Equivalently — and this is the grassfire picture — a point $p$ lies on the medial axis if and only if the circle centered at $p$ that just touches the boundary does so in at least two places. A disk touching the boundary at exactly one point is not maximal; it can still grow. Only when it presses against two or more boundary points at once does it reach its largest possible size, and its center joins the skeleton.

The medial axis keeps the topology intact. A simply-connected blob gives a tree skeleton. A ring gives a loop. Punch three holes and you get a branching graph. Strip away the radii and you lose thickness information, but the connectivity — the fundamental shape — is preserved. See also convex hull for another way geometry encodes a shape's essence.

The demo below runs a discrete grassfire on a pixel grid. Click {{btn_burn_label}} to ignite the boundary and watch wave-fronts spread inward. Pixels where two or more fronts collide at the same time are painted as the medial axis — the skeleton.

<!-- {{c_html_intro}} -->
<div class="toolbar">
  <span class="label">{{lbl_shape}}</span>
  <button id="btn-h"    type="button">H</button>
  <button id="btn-ring" type="button">{{btn_ring}}</button>
  <button id="btn-star" type="button">{{btn_star}}</button>
  <button id="btn-rect" type="button">{{btn_rect}}</button>
</div>
<canvas id="cv" width="300" height="300" title="{{canvas_title}}"></canvas>
<div class="toolbar">
  <button id="btn-burn"  type="button">{{btn_burn}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="status" class="status">{{status_ready}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.toolbar { display: flex; gap: .4rem; align-items: center; margin: .4rem 0; flex-wrap: wrap; }
.label { font-size: .85rem; color: #555; margin-right: .2rem; }
button { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #e63946; border-color: #c92f3c; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         image-rendering: pixelated; max-width: 300px; }
.status { font-size: .9rem; font-weight: 600; margin: .4rem 0; min-height: 1.3em; color: #1d3557; }
.status.done { color: #0a7d33; }

// Code not found

Notice that thin bridges produce long skeleton branches and wide bulges produce thick ones. Change the shape with the preset buttons and rerun to see how the skeleton captures the essence of each form. The grassfire reaches every interior pixel in time proportional to the shape's inradius — the radius of the largest inscribed circle.

Status: solved. Computing the medial axis of a polygon with $n$ vertices is equivalent to computing its interior Voronoi diagram — each boundary edge and vertex acts as a Voronoi site, and the medial axis is precisely the Voronoi diagram restricted to the interior of the shape. Fortune's sweep-line algorithm achieves $O(n \log n)$ time and $O(n)$ space, which is also the lower bound for comparison-based geometry.

The real challenge is not asymptotic complexity but numerical stability. The medial axis is notoriously sensitive to small bumps on the boundary:

• A tiny pimple on an otherwise smooth curve sprouts a long, thin skeletal branch that carries almost no geometric information.
• This is not a bug — it is mathematically correct. Small boundary features create their own medial-axis branches, no matter how insignificant they look.
• In practice, the medial axis must be pruned before use. The most common criterion is the significance measure or erosion thickness: a branch is kept only if it is generated by a maximal disk whose radius exceeds some threshold $\varepsilon$.

For curved shapes (smooth closed curves in the plane) the medial axis is still a graph, but computing it exactly requires handling parabolic arcs — the Voronoi edges between a point site and a line site are parabolas. Libraries such as CGAL and Boost.Polygon handle these. In 3D, the medial axis becomes a 2-dimensional surface (medial surface), and exact computation is substantially harder.

Despite the stability issue, the medial axis is central to pattern matching — matching two shapes becomes matching their skeletons, a far more tractable comparison.

The medial axis appears wherever a shape must be understood, navigated, or compared:

• Robot motion planning: a robot moving through a cluttered room can follow the medial axis of the free space — the path that keeps it maximally far from every obstacle at every step. This is the retraction method of motion planning.
• Medical image analysis: the centerlines of blood vessels, airways, and bones are medial axes. Measuring a coronary artery's narrowing, tracking tumor growth, or analysing bone density all rely on first extracting the vessel's or bone's skeleton.
• 3D printing and CNC machining: tool-path planning places the cutter head along the medial axis so the tool sweeps the interior with the fewest passes and avoids unnecessary boundary proximity.
• Font rendering and calligraphy: the stroke model of a letter is its medial axis plus a varying thickness function — the exact data a calligraphic font needs to rescale cleanly at any size.
• Shape retrieval and recognition: comparing two shapes by their medial-axis graphs is far more stable than comparing raw boundary contours. Database search for similar shapes (logos, biological cells, geographic outlines) routinely reduces to skeleton matching.
• Finite element meshing: decomposing a complex region into simple triangles for simulation is easier when the medial axis guides the decomposition, ensuring elements are well-shaped near narrow passages.

Set a shape on fire from its boundary. Where the flames collide, the skeleton appears. That simple picture — Blum's grassfire from 1967 — carries a surprising amount of mathematical weight: it preserves topology, encodes thickness, and reduces shape comparison to graph matching.

Computing the exact skeleton is efficient ($O(n \log n)$ via Voronoi diagrams), but using it wisely requires pruning away the noise that every real boundary introduces. Once pruned, the medial axis becomes one of the most versatile tools in computational geometry: it plans robot routes, measures arteries, guides 3D-printer heads, and gives calligraphic fonts their stroke.

The skeleton was hiding inside the shape all along. All it took was fire to reveal it.