A Brief Overview of Packing Problems

Abstract

Densely packed arrangements of objects of all shapes and sizes have captured the attention of scholars for many centuries. The iconic image of stacked cannonballs (Figure 1.1 and cover of this book) has come to symbolize this fascinating field. Such packings have raised numerous mathematical questions; with the advent of the digital age, they continue to challenge our computational techniques and algorithms. Many questions remain unresolved and stimulate further exploration of this captivating subject. As the range of packing problems has expanded, a related area of interest has emerged, focusing on the concept of tiling or tessellation (Figure 1.2). While packing involves positioning objects within a space, tiling partitions space into distinct compartments. For instance, foams (Chapter 10) can be considered as packings of deformable bubbles, which evolve into three-dimensional tilings when the liquid between the bubbles reduces to its minimum – essentially zero if the resulting soap films are regarded as possessing zero thickness (Figure 1.3). Point patterns, which might for example be made up of centres of packed spheres, can be converted to cellular structures by the Voronoi construction. There is a compelling argument for considering these two subjects as unified: often the analysis of a packing invokes a complementary tiling. Nevertheless, the present volume is focused mainly on packing.