Consider any collection of non-overlapping discs of equal
size (possibly just isolated points). We
associate to this collection a partition of the plane into regions called
Voronoi cells.
The Voronoi cell of a disc in the distribution is the set of
points in the plane which are as close or closer to the centre of that disc than to
the centre of any other disc in
the distribution.
The partition we associate to any distribution of non-overlapping discs in the plane is its Voronoi partition. We shall show that for any Voronoi partition the ratio of the area of a disc to the area of its cell is at most the ratio of a disc to its circumscribing regular hexagon. This will prove Thue's Theorem. |
This figure is live: the discs are movable. |
There are a few characteristic properties of Voronoi cells that we shall require.
(1) Since all the discs are of equal size, a disc is contained within its Voronoi cell. |
![]() |
(2) If |
(3) For a layout of three discs, the Voronoi cells will be simplicial cones with a common vertex at one point - the triple point - which is the common intersection of all three bisectors between the points - except in the singular case when the bisectors are mutually parallel. This triple point will be equi-distant from each of the three discs. Draw from the triple point the pair of tangent line segments to each of the discs, making a kind of dunce's cap. The vertex angle of that cap will be the same for each disc, since this angle depends only on distance of the triple point from the disc. Because Voronoi cells are convex, the whole of each cap will be contained in a the Voronoi cell of its disc. |
![]() ![]() |
|
|
Suppose we fix two of the three discs and ask
how this triple point varies as the third disc moves around.
If the two discs are far enough apart, the triple point can
be anywhere on the line bisecting the given pair.
But as soon as they are close enough together, there will be a
dead space on this line right in between the two
discs where the triple point
can never be found. This dead space will exist as soon
as the centres of discs are closer than ![]()
The figure also illustrates that
the caps drawn from the triple point
don't overlap (except possibly along their edges), and that
their common vertex angle can be
at most one-third of |
|
Circumscribe a disc with
a regular hexagon,
and circumscribe the hexagon with a circle.
This gives what I call the hexagonally
circumscribed circle of the original disc.
It is a concentric circle whose radius
is ![]() |
We shall need also another property of these circumscribed circles.
Suppose two of them intersect, but that the discs
themselves do not intersect. Then that intersection
can only intersect the Voronoi cell of
a third disc if the three discs are mutually touching
in the configuration of
discs in a hexagonal packing.
For suppose In the diagram to the right, this means that the points in the yellow rhombus are never in the Voronoi cell of the third disc. |
the hexagonally circumscribed circles. As a consequence, points in the yellow rhombus never lie in the Voronoi cell of a third disc. |
Suppose we now look at a cell in a layout. Draw the circumscribing circle as well, or at least its intersection with the cell. Where it extends beyond the cell, the line cut off by the cell boundary will be the bisector of the rhombus associated to two discs whose hexagonally circumscribed circles intersect.
We can now divide up the cell into distinct regions of three types:
![]() |
![]() |
![]() |
|
|
|
The density of the distribution in the first type of region is
of course |
But it can also be demonstrated by a purely
geometric argument.
The figure on the left above shows
the special case. In the figure on the right
the animation generates the other cases.
As the central angle decreases we also generate the image
of the left disc
under the unique
linear transformation which acts by scaling vertically
and horizontally, transforming
the original equilateral triangle to the narrower one, as
indicated in the figure above.
Linear transformations preserve ratios of areas.
The animation then shows how
the largest ratio of circular sector to triangle ocurs when
the central angle is
In summary, the
density will achieve the maximum possible only when there are no
regions of the first or third type and when the central
angle of each of the regions of type II is exactly
The analogous argument fails in 3D, since the smallest cell surrounding a sphere is known to be a regular dodecahedron, a shape which cannot partition all of space. In particular, as Kepler himself well knew and well described, this is not the same as the cell in the densest layout of spheres throughout all of space. It is this disparity between local and global behaviour that offers a serious obstacle to a simple proof of Kepler's conjecture in 3D.
I am greatly indebted to the staff at the Fisher Librray and especially the librarian, Richard Landon, for their cooperation in producing the images from Kepler's pamphlet that I have used.
The End