Piercing all translates of a set of axis-parallel rectangles

Adrian Dumitrescu ; Josef Tkadlec¹

¹Department of Mathematics, Harvard University, Cambridge, MA 02138, USA; and Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

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 $\mathcal{F}$. We denote the lowest possible density of such an $\mathcal{F}$-piercing point set by $\pi_T(\mathcal{F})$. Specifically, we focus on families $\mathcal{F}$ consisting of axis-parallel rectangles. When $|\mathcal{F}|=2$ we exactly solve the case when one rectangle is more squarish than $2\times 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 $|\mathcal{F}|\ge 2$ we present a linear-time constant-factor approximation algorithm for computing $\pi_T(\mathcal{F})$ (with ratio $1.895$).

Détail

DOI : 10.37236/12041

Classification : 52C05, 68W25
Mots-clés : axis-parallel rectangles