Optimal packings of coins and oranges

Abstract

The field of optimal packings belongs to the realm of "intuitive geometry" — a term introduced by László Fejes Tóth to describe geometry problems that are easy to state but extremely difficult to solve. Today, "difficult" often implies the need for computer assistance, as illustrated by the proofs of the Kepler conjecture and the four-color theorem. Such problems lie at the interface of the continuous and the discrete: to solve them, one must combine analytical (continuous) methods and computer calculations (discrete). A solid theoretical foundation is needed to make the computations feasible in terms of time and memory. The proofs of the Kepler conjecture and of the four-color theorem were eventually verified by computer, which is natural given that proofs of this magnitude are impossible to fully check by hand, and their significance made formal confirmation essential to the community. This inseparable triplet of complicated conjecture, computer assistance, and eventual formal verification will undoubtedly appear again in future results. In this article, we explore optimal disk and sphere packings, a domain that originated with the Kepler conjecture, where geometry and computation interact in various surprising ways.