Alpha Shapes

Imagine scattering a handful of sand on a table and then asking: what shape are those grains forming? If you draw the tightest shrink-wrap around them, you get the convex hull — a rubber-band outline that ignores every bay and hollow. But the real silhouette could be a crescent, a ring, a star, or something with fingers and holes.

Alpha shapes, introduced by Herbert Edelsbrunner, David Kirkpatrick, and Raimund Seidel in 1983, answer that question with one tunable parameter, $\alpha$ (alpha). Imagine rolling a disk of radius $r = 1/\alpha$ across the outside and inside of the point cloud. Any part of space that the disk can reach without touching a point gets carved away. What remains is the alpha shape.

• Set $\alpha = 0$ (infinite disk): nothing gets carved — you recover the full convex hull.
• Increase $\alpha$ (shrink the disk): the boundary starts to dip into concavities, revealing bays, peninsulas, and eventually holes.
• Increase $\alpha$ far enough: some points become isolated — the shape fragments into individual vertices.

The magic is that a single dial sweeps the full spectrum from "lump" to "skeleton" without any ambiguity. Alpha shapes sit at the heart of computational geometry and are the workhorse behind 3-D printing, molecular surface reconstruction, and geographic boundary estimation.

Click anywhere on the canvas to add points, then drag the alpha slider. The gray disk shows the rolling ball — wherever a disk of that radius fits without touching a point, the space is carved away.

<div class="controls">
  <label for="alpha-slider">{{label_alpha}}: <span id="alpha-val">0.05</span></label>
  <input type="range" id="alpha-slider" min="0" max="100" value="5" step="1">
  <span class="hint-label" id="shape-label">{{convex_hull}}</span>
</div>
<canvas id="canvas" width="460" height="320"></canvas>
<p class="hint">{{hint_paragraph}}</p>
<div class="btns">
  <button id="btn-preset" type="button">{{btn_load}}</button>
  <button id="btn-clear" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .4rem; }
label { font-size: .9rem; font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 260px; accent-color: #1d3557; cursor: pointer; }
.hint-label { font-size: .82rem; color: #1d3557; font-weight: 700; min-width: 110px; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f4f7fa;
         cursor: crosshair; touch-action: none; max-width: 100%; }
.hint { font-size: .84rem; color: #555; margin: .45rem 0; line-height: 1.45; }
.btns { display: flex; gap: .5rem; }
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; }

// Code not found

Notice the key transitions. When alpha is very small the disk is huge and nothing gets carved — you see the convex hull. As alpha grows the boundary tucks into concavities. Past a critical value the shape may split, and at very high alpha only the points themselves remain. The same cloud, endlessly different readings depending on the scale of the probe.

Computing alpha shapes looks expensive — you must decide, for every possible disk position, whether it can slip between the points. In practice the algorithm is elegant and provably optimal.

The key insight: the Delaunay triangulation. For a fixed set of n points, the Delaunay triangulation partitions the plane into triangles so that no point lies inside any triangle's circumcircle. This structure encodes all alpha shapes simultaneously:

• A triangle (face) belongs to the alpha shape if and only if its circumradius $\le 1/\alpha$.
• An edge belongs if its circumradius $\le 1/\alpha$ (the circumcircle of the two-point "Gabriel circle").
• A vertex always belongs (for any finite $\alpha$).

So the full algorithm is:

1. Build the Delaunay triangulation: $O(n \log n)$ — optimal for comparison-based planar geometry.
2. For each simplex (vertex, edge, triangle), record its circumradius.
3. For any query $\alpha$, filter to simplices with circumradius $\le 1/\alpha$: $O(n)$.

The result is the alpha complex — a subcomplex of the Delaunay triangulation — whose boundary is the alpha shape. This construction was proven correct and optimal by Edelsbrunner, Kirkpatrick & Seidel (1983), making alpha shapes a solved problem in computational geometry.

The related alpha-hull concept generalises to higher dimensions, where the Delaunay structure remains the backbone and the complexity stays $O(n^{\lceil d/2 \rceil})$ in $d$ dimensions — polynomial but growing fast.

The ability to recover a shape's true boundary from scattered samples shows up everywhere:

• 3-D surface reconstruction: laser scanners and photogrammetry produce raw point clouds. Alpha shapes turn millions of unordered points into a watertight mesh for 3-D printing or game assets.
• Molecular biology: the solvent-accessible surface of a protein is exactly the boundary swept by a water-molecule-sized ball rolling over the van der Waals radii of atoms — the Connolly surface is an alpha shape.
• LiDAR and autonomous vehicles: street-level point clouds are filtered into road surfaces, building outlines, and tree canopies using alpha-shape extraction at different radii.
• Geographic information systems (GIS): given GPS tracks or field measurements, alpha shapes give a non-convex polygon boundary of the surveyed region — far more accurate than a convex hull for elongated coastlines or archipelagos.
• Computer graphics and collision detection: alpha shapes identify the concave hull of a 2-D sprite or a 3-D character, enabling tighter bounding volumes and faster collision queries than axis-aligned boxes.
• Outlier detection: points that belong to the alpha complex only at very high alpha values are geometrically isolated — natural candidates for flagging as noise or anomalies.

Wherever you have samples and need a boundary, alpha shapes let you tune how much boundary you want — from the coarsest enclosure to the finest detail the data supports.

Alpha shapes give a beautiful answer to a deceptively hard question: what shape is this cloud of points? By rolling a disk of tunable radius and carving away anything the disk can reach, they sweep the full range from convex hull to fine skeleton with a single dial.

The Delaunay triangulation makes the computation optimal — build the structure once in $O(n \log n)$, then answer any alpha query in $O(n)$. That combination of geometric elegance and computational efficiency is why alpha shapes, invented in 1983, remain the standard tool for surface reconstruction four decades later.

Next time you see a 3-D printed object or a protein structure viewer, there's a good chance an alpha shape — and one carefully chosen radius — decided exactly where the boundary lies.