Office of Technology Transfer – University of Michigan

Methods and Algorithms to Optimally Fill Shapes

Technology #5301

Shape-filling Given an arbitrary shape, how to optimally pack overlapping objects inside the shape so as to cover the most interior volume without extending beyond the boundary of the shape is an abstract mathematical problem that has broad applications in many disciplines. For example, such filling could arise from the problem of modeling anisotropic nanoparticles as rigid bodies composed of a sum of isotropic volume-excluding potentials. Other applications include the problem of irradiating a tumor with the fewest number of beam shots, while controlling the beam diameter, but without damaging surrounding tissue; combining precision-placed explosives with tunable blast radii; positioning proximity sensors with defined radii; cell phone and wireless network coverage; or any problem of ablation or deposition where one has a sharp impenetrable boundary and a radially tunable tool.

Optimized filling based on the medial axis technique A research group in the Chemical Engineering of University of Michigan has reported a new kind of method for optimally placing objects in space, which is called the optimization “filling” a shape. In n-dimensional space, if the objects are polydisperse n-balls, solutions correspond to sets of maximal n-balls whose centers lie on the medial axis hypersurface. For two dimensional simple polygons, the group provides a heuristic and a genetic algorithm for finding solutions of maximal discs (2-balls). Researchers also provide an expression for ideal distribution of N of these discs as N approaches infinity. In three-dimensions, the group proposes a simulated annealing method coupled with a gradient method to find optimal solutions in convex polygons.

Application • Nanoparticles modeling and simulation • Wireless network (or sensors) optimal coverage

Advantages • Guaranteed optimality of the solutions • Efficiency of the implementation