Revisiting the hexagonal lattice: on optimal lattice circle packing

02/02/2010 - 12:15pm
02/02/2010 - 1:10pm
Lenny Fukshansky (CMC)

The classical circle packing problem asks for an arrangement of non-overlapping circles in the plane so that the largest possible proportion of the space is covered by them. This problem has a long and fascinating history with its origins in the works of Albrecht Durer and Johannes Kepler. The answer to this is now known: the largest proportion of the real plane, about 90.7%, is covered by the arrangement of circles with centers at the points of the hexagonal lattice. Although there were previous claims to a proof, it is generally believed that the first complete flawless argument was produced only in 1940 by Laszlo Fejes-Toth. On the other hand, the fact that the hexagonal lattice gives the maximal possible circle packing density among all lattice arrangements has been known at least as early as the end of 19-th century; in fact, all the necessary ingredients for the first such proof were present already in the work of Lagrange. In this talk we outline a modern proof of this classical result, which emphasizes the importance of well-rounded lattices for discrete optimization problems.

Millikan 208 (Pomona College)