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.

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.

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.

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]