Matpic
mathematics, in pictures
Concept

Delaunay triangulation

The triangulation of a set of points in which no triangle's circumcircle contains any other point. It is the dual of the Voronoi diagram, it maximises the smallest angle, and it contains the shortest spanning tree of the same points.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

The plane divided by nearest neighbour. 10 sites, and every point of the rectangle shaded by which site is closest to it. The boundaries are the places where two sites tie.

The plane, divided by whoever is nearest

Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.

geometry · Voronoi The triangulation as the underside of a hull. Eight points on a floor, lifted onto a paraboloid above them. The faces of the lifted set's lower convex hull are shaded, and their shadows on the floor are the Delaunay triangulation of the original points.

One dimension up, and the circles disappear

The Delaunay triangulation is defined by a condition about circles, which is awkward to compute and awkward to reason about. Lift every point onto a paraboloid and the circles turn into planes, the condition turns into convexity, and a two-dimensional problem is solved by looking at a three-dimensional shape from underneath.

geometry · Voronoi The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi The medial axis of a wobbly rectangle, whole and trimmed. A rectangle with sides wobbling by ±0.02: its medial axis (654 Voronoi vertices, Hausdorff distance 0.499 from the clean axis) and its λ-medial axis at λ = 0.2 (63 vertices, distance 0.078).

A skeleton that ignores small teeth

The medial axis of a shape grows a branch to every bump on its outline, however small, so a scanned shape has a skeleton made mostly of noise. Keep only the points of the axis whose nearest boundary points are spread across a circle of radius at least λ, and the branches to bumps smaller than about 2λ disappear while the real skeleton stays. That λ-medial axis moves only a little when the outline wobbles by much less than λ — and the price is λ itself, a size below which a feature is declared not to exist, which can even cut a shape's skeleton in two.

geometry · Voronoi

Named alongside it

The objects these essays reach for when they reach for this one.

Voronoi diagramCircumcircleConvexityDualityPlanar graphCircleComplexityConvex hullEuler characteristicGraphGreedy algorithmHausdorff distance

All concepts