Piercing All Translates of a Set of Axis-Parallel Rectangles

For a given shape S in the plane, one can ask what is the lowest possible density of a point set P that pierces ("intersects", "hits") all translates of S. This is equivalent to determining the covering density of S and as such is well studied. Here we study the analogous question for families of shapes where the connection to covering is altered. That is, we require that a single point set P simultaneously pierces each translate of each shape from some family F. We denote the lowest possible density of such an F-piercing point set by πT(F). Specifically, we focus on families F consisting of axis-parallel rectangles. When |F|=2 we exactly solve the case when one rectangle is more squarish than 2× 1, and give bounds (within $10\,%$ of each other) for the remaining case when one rectangle is wide and the other one is tall. When |F|≥ 2 we present a linear-time constant-factor approximation algorithm for computing πT(F) (with ratio $1.895$).