Matpic
mathematics, in pictures
Concept

Convex hull

The smallest convex set containing a given collection of points, which is what an elastic band snapped round them would enclose. Its corners are exactly the points that are not mixtures of the others, and finding them is the basic problem of computational geometry.

Named by 4 essays across 2 fields — 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 diagram when the sites are not the same size. 7 weighted sites drawn as circles of different radius, with the power diagram over them. The boundaries are straight, as in the unweighted diagram, but each one is pushed towards the smaller of the two circles it separates.

When the sites are not the same size

Give every site a weight and the boundaries slide. The cells stay convex and the edges stay straight, which is surprising, and one thing happens that the unweighted diagram never allows — a site can end up owning nothing at all.

geometry · Voronoi The two numbers that make up a width. A Reuleaux polygon with 3 sides, its centre marked as the origin, and the two supporting lines with normals 33° and 213°. The perpendicular distances from the origin to the two lines are marked; they add to the width.

The shape described from outside

A convex shape can be given by its boundary or by the family of lines that touch it, and the second description turns the constant-width condition into one line of arithmetic — after which the perimeter falls out, and curves with no corners at all can simply be written down.

geometry · Constant width The 14 triangulations, joined by single flips. The flip graph of a 6-gon: 14 triangulations drawn as small polygons and joined by 21 edges, one for each pair differing in a single diagonal.

The solid whose corners are triangulations

Take the triangulations of a hexagon as points and join two of them when a single diagonal can be swapped for another. The result is not merely a graph — it is the edge skeleton of a genuine convex polyhedron, with fourteen corners, three square faces and six pentagonal ones.

discrete · Catalan numbers

Named alongside it

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

ConvexityDualityLifting mapVoronoi diagramAssociativityCatalan numbersCircleCircumcircleConstant widthCurvatureDelaunay triangulationEuler formula

All concepts