Skip to Main Content

Packing Pennies in the Plane

6. How dense can a disc be in its Voronoi cell?

We want to show that a disc take up no larger proportion of the area in its Voronoi cell than it does in its circumscribing regular hexagon. To show this, we partition the cell into sub-regions of different types.

Suppose we now look at a cell in a layout.Draw the circumscribing circle as well, or at least itsintersection with the cell. Where it extends beyondthe cell, the line cut off by the cell boundarywill be the bisector of the rhombus associated to two discs whose hexagonally circumscribed circles intersect.

We can now divide up the cellinto distinct regions of three types:

The points in the cellwhich do not belong tothe enlarged disc
The points in the celllying in a rhombus associated toa neighbouring cell.
The parts of the circumscribing disc notbelonging to one of these rhomboi.

The density of the distribution in the first type of region is of course 0, since by definition such a region contains no part of a disc. The density of the distribution in the third type is just the ratio of the radius of the disc to that of the larger one. Both densities are strictly less than the density of the disc in its regular circumscribed hexagon. The crux of the argument is now to examine regions of the second type.

Partitioning several cells. This image is `live'.