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

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×2 and 2×1 even when every rectangle intersects a given unit height horizontal strip.