Matpic
mathematics, in pictures
Concept

Circumcircle

The unique circle passing through the three corners of a triangle, centred where the three perpendicular bisectors meet. Whether it is empty of other points is the condition defining the Delaunay triangulation.

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

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.

Delaunay triangulationVoronoi diagramComplexityConvex hullConvexityDualityGraphGreedy algorithmLifting mapParaboloidPlanar graphSpanning tree

All concepts