Tikalon Header

Packing and Filling

May 17, 2012

I wrote about packing in a previous article (Packing, November 30, 2010). When my wife and I were first married, one of the first problems we faced was a packing problem. We needed to combine all our possessions into a single small apartment. After the initial condition, the situation was self-regulating, since students never have much money to buy additional household items.

Secure transmission of data without the encumbrance of key transfer is an important part of the Internet. We wouldn't want our financial information zipping along through multiple routers unprotected. The packing process was viewed as an early means for public key encryption of data. The Merkle–Hellman knapsack cryptosystem is a public key cipher that's based on the knapsack problem, the idea of which is the optimal packing of items in a knapsack (backpack, rucksack).

The knapsack problem a "one-way" problem; that is, it's easier to take items out of an optimally packed sack than putting them back in. It can be idealized mathematically as the subset sum problem of building a subset whose sum is zero from a set of integers. For example,
Set: {-22, -5, -3, -2, 1, 3, 4, 7, 9, 14, 18)
Subset: {-22, -5, -2, 4, 7, 18}

In the end, the system that was actually used was the different one-way problem that it's easier to multiply large numbers than factor them. This encryption method is used on the web browser that you're using to view this article, even if you're using certain versions of the Lynx web browser.

An optimal packing of pennies on a plane occurs when their centers are on an hexagonal lattice, giving an areal density of (π/2√3) = 0.9069 (see figure). This was proven mathematically by Carl Friedrich Gauss for such a lattice packing; and László Fejes Tóth showed that this is the optimal packing, lattice or otherwise.[1]
Lattice packing of pennies in a planeLattice packing of pennies in a plane.

These are Wikipedia pennies, the payment I get for writing Wikipedia articles.

(Based on a Wikimedia Commons image).

The idea of arranging circles so that they have a maximum areal density can be extended to filling geometrical figures; and there's a similar problem of filling geometrical figures with overlapping circles of selected diameters to fill as much of the area as possible (see figure). This filling problem is discussed in a recent paper in Physical Review Letters by an interdisciplinary team of scientists from the University of Michigan and the University of Connecticut.[2-5]
Figure caption(Illustration by author, rendered with Inkscape).
Filling is an intermediate problem between packing and covering. Covering is the problem of completely covering the surface area of an object with appliqués of a given shape and size. Filling differs from the covering problem, since the applied shapes can't extend over the shape's perimeter.[5] An example of the filling problem was given in a synopsis of this paper on the American Physical Society web site.
"Imagine you have a square window and you want to block out as much light as possible by taping some opaque circular tiles to the glass. You can use a mixture of tiles with any radius, and they can overlap with each other, but you only have money to buy five."[4]
More technically, filling can be describes as the way you can place N overlapping circles of any size within a bounded area to best fill its area.

In looking at the filling example of the triangle in the figure, above, you get the idea that there are special lines on which such circles should be placed. These are called the medial lines. Sharon Glotzer, an author of the study, describes the medial line as the "backbone" of the polygon. Said Glotzer, "Every shape you want to fill has a backbone that goes through the center of the shape, like a spine."[5] An example of the medial lines for a concave polygon and its filling by twenty-one discs are shown in the following figure.
Figure caption
Fig. 2 of reference 3, modified, showing the medial lines for a concave polygon and an optimal filling with twenty-one discs. (Via arXiv Preprint Server).[3]

It's always nice when research provides a tangible benefit. There are quite a few applications for an effective filling algorithm. The equipment used for radiation treatment of tumors allows control of the beam diameter, so this may be a method for effective treatment with the lowest number of beam shots.[2-3]

It would also allow optimal mapping of cell telephone towers for best coverage, and programming of ion beams for the best definition of a shape in ion-milling or ion-deposition.[2-3] The research team is polishing an algorithm that will take as an input a desired shape and the number of discs, and it will output the best disc pattern.[5]

References:

  1. Weisstein, Eric W. "Circle Packing." From MathWorld--A Wolfram Web Resource.
  2. Carolyn L. Phillips, Joshua A. Anderson, Greg Huber and Sharon C. Glotzer, "Optimal Filling of Shapes," Physical Review Letters, vol. 108, no. 19 (May 11, 2012), Document No. 198304, 5 pp..
  3. Carolyn L. Phillips, Joshua A. Anderson, Greg Huber and Sharon C. Glotzer, "Optimal Filling of Shapes," arXiv Preprint Server, February 11, 2012.
  4. Jessica Thomas, "Thinking Inside the Box," Synopsis of Ref. 2, American Physical Society.
  5. Katherine McAlpin, "New twist on ancient math problem could improve medicine, microelectronics," University of Michigan Press Release, May 10, 2012.