Matpic
mathematics, in pictures
Series

Voronoi — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · geometry
  2. 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.

    part 2 · geometry
  3. A scatter walking towards its own centres. 4 panels of the same 24 sites: the initial clumpy scatter and the Voronoi diagram after 1, 3, 12 rounds of Lloyd's iteration, with the cost falling to 52% of the scatter's as the cells even out.

    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.

    part 3 · geometry
  4. 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.

    part 4 · geometry
  5. 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.

    part 5 · geometry

All series