We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
AN APPROXIMATION ALGORITHM FOR LOCATING MAXIMAL DISKS WITHIN CONVEX POLYGONS.
- Authors
AOTA, HIROFUMI; FUKUNAGA, TAKURO; NAGAMOCHI, HIROSHI; Fekete, Sandor
- Abstract
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 the disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap with each other. We present an approximation algorithm for this problem assuming that the container is a convex polygon. Our algorithm achieves approximation ratio (0.78 - ϵ) for any small ϵ > 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.
- Subjects
HEURISTIC; APPROXIMATION algorithms; MAXIMA &; minima; POLYGONS; SET theory; DIMENSIONAL analysis; MATHEMATICAL formulas
- Publication
International Journal of Computational Geometry & Applications, 2011, Vol 21, Issue 6, p661
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195911003858