[seqfan] Voronoi diagrams of square lattice with a small number of voids

Allan Wechsler acwacw at gmail.com
Thu Dec 14 00:05:20 CET 2017

The Voronoi diagram of a square lattice is the familiar tiling of square
cells. If we delete one node in the lattice, a new cell-shape appears, a
house-shaped pentagon.

If we delete two points from the square lattice, then, depending on the
relative positions of the deleted points, we can obtain three new shapes, a
pentagon that looks a bit like a punch-card, another pentagon that looks
like home plate in baseball, and a lozenge-like hexagon.

Deleting three points can give rise to 6 new shapes: a rectangle, three
pentagons, a hexagon, and an octagon.

Starting with no deletions, the number of shapes that can arise from the
interaction of n deletions is (1, 1, 3, 6, 14, 28 ...). I am not completely
confident of the 28.

This sequence has two matches in OEIS, but neither has anything to do with
square lattices or Voronoi domains. Can I interest anybody in calculating
A(6)? That is, how many shapes arise in the Voronoi diagrams of square
lattices with six deletions, that cannot be created with fewer deletions? I
consider two shapes to be different if they are not geometrically congruent.

More information about the SeqFan mailing list