Frank Morgan

Relaxed Disk Packings

by John Berry, Matthew Dannenberg, Jason Liang, and Yengyi Zeng
2015 NSF “SMALL” undergraduate research Geometry Group

With update below by Iglesias-Ham (all already known).

Abstract. The classic result about the optimal hexagonal packing of unit disks in the plane has recently been partially generalized by Edelsbrunner et al. to allow but penalize overlap for the case of lattice packings. We attempt to remove the restriction to lattice packings.

1. Introduction. Recently, Edelsbrunner, Iglesias-Ham and Kurlin [EIK] considered a relaxed packing problem in which disks are allowed to overlap and the goal is to maximize the probability that a random point is contained in exactly one disk. They found that among all relaxed lattice packings of congruent disks in R², a regular hexagonal packing with disks of a unique radius maximizes this probability. We attempt without success to remove the lattice hypothesis by generalizing Thomas Hales’s proof [H1, H2] of Thue’s Theorem, which is based on an idea of Rogers [R]. The key to Hales’s proof is to partition the plane into three regions and show that the density of disks inside each region is no more than the hexagonal packing density, but when we allow disks to overlap, the density of disks inside one of the regions is larger than the relaxed hexagonal packing. Acknowledgements 1.1. This paper is the work of the Williams College NSF “SMALL” 2015 Geometry Group. We thank our advisor Professor Morgan for his support. We would like to thank the National Science Foundation, Williams College, and the MAA for supporting the SMALL REU and our travel to MathFest 2015.

Continue reading paper.

Dear Frank Morgan,

Recently, while working in our camera ready, we learnt about some old results relevant to our paper:

– Fejes Toth in his book ‘Regular Figures’, 1965, posed the very same version of relaxed packing we address in our paper. He conjectured that indeed the regular hexagonal lattice would provide the optimal configuration when the radius is such that disks intersect each of the six neighbors in 30 degrees arcs. Moreover, he claims Bal’azs proved it for lattices in an unpublished paper back then.

–  Bal’asz, 1973, published an article with the proof of the result for 2D lattices (“Ueber ein Kreisueberdeckungsproblem,”Acta Math. Acad. Sci. Hungar. 24, 377-382).

– Blind, G. and Blind, R, in 1986, proved the regular hexagonal lattice is still optimal among any distribution of disks. (“Ein Kreisueberdeckungsproblem,” Studia Sci. Math. Hungar. 21, no.1-2, 33-57 ).

– Blind, G. and Blind, R, in 1994, studied the same optimization problem for disks lying on a sphere (“Ein Kreisueberdeckungsproblem auf der Sphere,” Studia Sci. Math. Hungar. 29, no. 1-2, 107-164).

I thought as you have students working on the topic this information may interest you. Unfortunately, we have been working on a solved problem.

Best Regards,
Mabel

Thanks to Iglesias-Ham for allowing us to reprint her message here.