Packing and Covering

Geometry Definitions >

Packing and covering deal with arranging geometric objects like circles, squares and triangles within a specified region, like a unit sphere. These optimization problems are used to find minimums and maximums of objects, radii or other features of the object or the space they are contained within.

They approach similar questions in different ways. The focus with packing is on an arrangement’s density—the ratio of total volume of the members in the arrangement to the volume of the entire space. As an example (Gaspar et al., 2014), a packing problem might be: How can n circles of equal size be packed into a unit circle so that the circles radius is the maximum size? On the other hand, covering is concerned with the thinnest covering. The above question could be reworded to become a covering problem instead: How can n equal circles cover the unit circle, without interstices (spaces in between) so that their radius is as small as possible?

Despite the apparent simplicity of the questions posed with packing and covering, most of the problems are actually quite challenging to solve. The Kepler conjecture is a famous example of a sphere packing problem which has stumped mathematicians for centuries. Johannes Kepler claimed that no arrangement of spheres of equal radius in three dimensions has a greater density than the face-centered cubic lattice.

Packing and Covering: Real Life Applications

In real life, packing problems can be used to find the optimal packing for constrained spaces. For example, how to efficiently pack and ship boxes of tennis balls, cylinders or cables so that the space is maximized. Packing can also be used to find the best locations for cell phone towers, given that they are unwanted in some areas (e.g. residential neighborhoods) and tolerated in others (e.g. highway routes).

References

Ene, A. et al. (2011). Geometric Packing under Non-uniform Constraints.
Gaspar, A, et al. (2014). Partial covering of a circle by equal circles. Part I: The mechanical models. Journal of Computational Geometry.
Toth, G. Packing and Covering. Retrieved February 4, 2021 from: http://www.csun.edu/~ctoth/Handbook/chap2.pdf