Generator

The plane divided by nearest neighbour

A generator in the geometry library, called 45 times across 8 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

voronoi is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

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 medial axis of a wobbly rectangle, whole and trimmed

Three points of a medial axis and how far apart their nearest boundary points are

How far the medial axis moves when the outline wobbles, with and without λ

Spurious branches against lost ones, as λ rises

The λ that removes a tooth's branch, against the tooth's size

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the centre of cell 0 is nearest to site 0 ×20
a large λ loses the corner arms ×1
a maximal disc contains no boundary point in its interior ×1
a planar triangulation of n points has at most 3n − 6 edges ×1
a point is under the chord exactly when it is inside the interval ×1
a site has a cell exactly when its lifted point is a corner of the lower hull ×1
a site inside the circle is nearer to both ends than the ends are to each other ×1
a spanning tree has one edge fewer than it has sites ×1
a λ-medial axis barely moves while the wobble is under a tenth of λ ×1
an axis point on a corner arm exists ×1
an axis point on a trunk exists ×1
an axis point on a wobble branch exists ×1
an intermediate λ balances spurious branches against lost ones ×1
and at least enough to be connected ×1
and jumps once the wobble passes about a fifth of λ ×1
and so the refuted edge is not in the shortest tree after all ×1
at least one pair of circles actually crosses ×1
at least one site has no cell, which is what the picture is about ×1
below it the axis is one piece ×1
between 2 and 60 sites, each a point in or near the unit square ×1
by the largest count drawn, the pairs outnumber the triangulation's edges several times over ×1
each graph in the chain has no more edges than the next ×1
each panel is on the side of the threshold the figure claims ×1
every Delaunay triangle spans a face of the lower hull ×1
every edge of the minimum spanning tree is an edge of the triangulation ×1
every Gabriel edge is a Delaunay edge ×1
every Lloyd step lowers the total squared distance to the nearest site ×1
every lower face projects to a Delaunay triangle ×1
every nearest neighbour edge is a shortest tree edge ×1
every relative neighbourhood edge is a Gabriel edge ×1
every shortest tree edge is a relative neighbourhood edge ×1
every site keeps a cell ×1
every upper face's circumcircle contains every other site ×1
exactly one of the two triangulations is the Delaunay one ×1
more than half of the whole fall happens in the first two rounds ×1
most interior cells settle at six sides, by more than double the next count ×1
no point beats the centroid ×1
no triangle's circumcircle holds another site ×1
the axis comes apart once λ passes the neck's half-width ×1
the axis has been found ×1
the bisector is where the two distances tie ×1
the cells account for the whole box, with nothing double-covered ×1
the cells still account for the whole box ×1
the chain is not a chain of equalities ×1
the circle on a tree edge as diameter holds no other site ×1
the circumcircle verdict and the lifted-hull verdict agree ×1
the cost falls at every round ×1
the edge chosen to be refuted really does have a site inside its circle ×1
the farthest-point triangulation uses only sites on the convex hull ×1
the gap between chord and parabola is −(x − a)(x − b) ×1
the highlighted cell is one of the sites ×1
the interior Voronoi corners of boundary samples lie along the medial axis ×1
the iteration has actually moved, rather than starting at its own fixed point ×1
the lift finds as many triangles as the circumcircle test does ×1
the middle cell is absent at the small weight and present at the large one ×1
the middle of each cell has that cell's site nearest in the power distance ×1
the moment about the site is the moment about the centroid plus area times the gap squared ×1
the settled cells are far closer to equal in area than the scatter's ×1
the settled diagram holds a larger share of six-sided interior cells ×1
the shape is one this family knows ×1
the tested point is inside the interval, which is what makes the pair illegal ×1
the triangulation is not empty ×1
the trunk's nearest points are spread widely, the wobble branch's are bunched ×1
the whole axis jumps far at the smallest wobble ×1
the whole axis wanders far from the clean rectangle's, the λ-axis stays close ×1
the λ that cuts the tooth's branch grows in proportion to the tooth ×1
where two circles cross, the two power distances agree ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Geometry

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

Every site in the middle of its own cell

Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.

Geometry

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

Nine points on one circle

Three midpoints, three feet of altitudes and three more midpoints. Nine points defined in three unrelated ways, on an arbitrary triangle, and all nine sit on one circle — checked here on two hundred and forty triangles as well as on the drawn one.

Geometry

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

The skeleton inside a shape

Take the Voronoi diagram not of a handful of points but of a shape's whole outline: the points inside the shape that have two nearest points on its edge. What comes out is a skeleton — a thin branching tree that describes the shape and, with one number attached to each point, rebuilds it exactly. It is also where fires lit all round the edge would meet, and it is violently unstable: a tooth too small to notice grows a branch several times its own size.

Geometry

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

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.

The whole library · What the figures prove