Abstract

In the Independent Set of Convex Polygons problem we are given a set of weighted convex polygons in the plane and we want to compute a maximum weight subset of non-overlapping polygons. This is a very natural and well-studied problem with applications in many different areas. Unfortunately, there is a very large gap between the known upper and lower bounds for this problem. The best polynomial time algorithm we know has an approximation ratio of and the best known lower bound shows only strong -hardness. In this paper we close this gap, assuming that we are allowed to shrink the polygons a little bit, by a factor for an arbitrarily small constant , while the compared optimal solution cannot do this (resource augmentation). In this setting, we improve the approximation ratio of to which matches the above lower bound that still holds if we can shrink the polygons.