Title: Range Assignment of Base-Stations Maximizing Coverage Area without Interference,
Abstract: We study the problem of assigning non-overlapping geometric objects centered
at a given set of points such that the sum of area covered by them is
maximized. If the points are placed on a straight-line and the objects are
disks, then the problem is solvable in polynomial time. However, we show that
the problem is NP-hard even for simplest objects like disks or squares in
${\mathbb{R}}^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 ${\mathbb{R}}^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 dimensions. All these
approximation results hold for the area maximization problem by regular convex
polygons with even number of edges centered at the given points.