Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-017 (December 14, 2010)

Dynamic Programming Based Approximation Scheme for Locating Disks within Convex Polygons
by Hirofumi Aota, Takuro Fukunaga, Hiroshi Nagamochi

pdf File

This paper considers a problem of locating the given number of disks into a container so that the area covered by the disks is maximized. In the problem, the radii of disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap each other. We present an approximation scheme for this problem assuming that the container is a convex polygon. Our scheme gives a (0.78-epsilon)-approximation algorithm for any small epsilon>0. Since the computation time of our algorithm depends on the number of corners of the convex polygon exponentially, we also give a heuristic to reduce the number of corners.