Approximability and hardness of geometric hitting set with axis-parallel rectangles

摘要

We show that geometric hitting set with axis-parallel rectangles is APX-hard even when all rectangles share a common point. We also show that geometric hitting set problem is APX-hard for several classes of objects given in [3] such as axis-parallel ellipses with a shared point, axis-parallel cubes sharing a common point, etc.Further, we give a polynomial time approximation scheme (PTAS) for the weighted hitting set problem with axis-parallel rectangles when all rectangles have integer side lengths bounded by a constant C. Finally, we show that the problem is NP-hard for rectangles of size 1 x 2 and 2 x 1 even when every rectangle intersects a given unit height horizontal strip. (C) 2018 Elsevier B.V. All rights reserved.