Computational Geometry (cs.CG)

  • PDF
    This note is a study on the problem of assigning non-overlapping disks centered at a set of given points in ${\IR}^2$ such that the sum of area covered by them is maximized. If the points are placed on a straight-line, then the problem is solvable in polynomial time. However, the problem is shown to be NP-hard in ${\IR}^2$. Eppstein [CCCG, pages 260--265, 2016] proposed a polynomial time algorithm for maximizing the sum of radii (or perimeter) of non-overlapping balls or disks when the points are arbitrarily placed on a plane. We show that Eppstein's algorithm for maximizing sum of perimeter of the disks in ${\IR}^2$ gives a $2$-approximation solution for the sum of area maximization problem. We propose a PTAS for our problem. These approximation results are extendible to higher dimension. All these approximation results hold for the area maximization problem by regular polygons with even number of edges centered at the given points.