Lattice and Non-lattice Piercing of Axis-Parallel Rectangles: Exact Algorithms and a Separation Result

arXiv2204.10385MaRDI QIDQ6397141FDOQ6397141

Authors: Adrian Dumitrescu, Josef Tkadlec 

Publication date: 21 April 2022

Abstract: For a given family of shapes $mathcalF$ in the plane, we study what is the lowest possible density of a point set $P$ that pierces ("intersects", "hits") all translates of each shape in $mathcalF$. For instance, if $mathcalF$ consists of two axis-parallel rectangles the best known piercing set, i.e., one with the lowest density, is a lattice: for certain families the known lattices are provably optimal whereas for other, those lattices are just the best piercing sets currently known. Given a finite family $mathcalF$ of axis-parallel rectangles, we present two algorithms for finding an optimal $mathcalF$-piercing lattice. Both algorithms run in time polynomial in the number of rectangles and the maximum aspect ratio of the rectangles in the family. No prior algorithms were known for this problem. Then we prove that for every $ngeq3$, there exist a family of $n$ axis-parallel rectangles for which the best piercing density achieved by a lattice is separated by a positive (constant) gap from the optimal piercing density for the respective family. Finally, we sharpen our separation result by running the first algorithm on a suitable instance, and show that the best lattice can be sometimes worse by $20\mathrm{\%}$ than the optimal piercing set.

This page was built for publication: Lattice and Non-lattice Piercing of Axis-Parallel Rectangles: Exact Algorithms and a Separation Result

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6397141)