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 3 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

Named alongside it

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

Voronoi diagramCircumcircleConvexityDualityPlanar graphCircleComplexityConvex hullEuler characteristicGraphGreedy algorithmLifting map

All concepts