Generator

The plane divided by nearest neighbour

A generator in the geometry library, called 32 times across 6 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.

A scatter walking towards its own centres

Every site, and the middle of its own cell

Where the cost actually falls

What the iteration settles into

Where two sites tie

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 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
and at least enough to be connected ×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
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 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 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 tested point is inside the interval, which is what makes the pair illegal ×1
the triangulation is not empty ×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

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