Think Deeply about Simple Things (with Computation) - or - Optimal Filling of Shapes

Carolyn Phillips, Argonne National Laboratory

Given a shape, what is the most effective way to pack balls of different sizes inside to fill as much of the shape as possible? What if the balls can freely overlap but must stay inside the walls of the shape?  This puzzle, which we call the filling problem, combines two classic problems of mathematical physics: sphere packing and covering. However, solutions to the filling problem are distinctly different. For a three-dimensional shape, the balls could be droplets, bubbles, or simply low-information objects that are easy to model. For two-dimensional shapes filled with discs, the discs could represent laser beams, wave fronts, or sensor ranges. In this talk, we explore the mathematical space of filling solutions and consider how optimal solutions can be constructed. We present both a genetic and a heuristic algorithm for finding the best possible filling solutions of polygons. We also consider how overlapping discs fill a polygon as the number of discs approaches infinity. In three dimensions, many open questions remain to be solved for this rich new problem. 

Abstract Author(s): Carolyn Phillips