# "Fast" approximation algorithm for geometric hitting set of same-height rectangles

In the Geometric Hitting Set problem, we are given a set of $$m$$ geometric objects and a set of $$n$$ points in $$\mathbb{R}^2$$, and we wish to find a small subset of the points that hits all the objects.

Geometric Hitting Set has a PTAS running in time $$mn^{O(1/\epsilon^2)}$$ for various types of geometric objects, including pseudo-disks and same-height rectangles (Mustapha-Ray, 2010).

I am interested in approximation algorithms that achieve a constant-factor approximation, but that run relatively fast, say, $$O((m+n)^{20})$$. For example, for pseudo-disk objects, such algorithms exist (Bus-Garg-Mustapaha-Ray, 2015).

My question: does there exist a comparable algorithm for same-height rectangle objects?

• How much fast? since for $\epsilon = 1/2$, $m \cdot n^{1/\epsilon^2} \in O((m+n)^4)$ already... May 24, 2021 at 19:13
• Ah sorry, the running time is actually $mn^{O(1/\epsilon^2)}$, not $O(mn^{1/\epsilon^2})$. Indeed otherwise the question is rather meaningless! Thanks for the comment. May 24, 2021 at 19:24
• For geometric packing and covering, one can use LP based approaches in place of local search. One can solve the LP relaxations fast using various techniques. See for instance dl.acm.org/doi/abs/10.5555/3381089.3381151 and pointers and other recent work by Timothy Chan and others. May 24, 2021 at 23:55
• Thanks, @ChandraChekuri ! These results seem indeed to answer my question, although it's not crystal clear which result applies to the setting of my question (same-height rectangle hitting set), and with which running time, but I'll look into it. If you, or someone else, can give more details, I'll accept it as an answer. May 25, 2021 at 9:14
• @FlorentFoucaud For LP solving general rectangles are also easy. It is only in the rounding stage that unit height rectangles are better behaved. I am guessing that unit height rectangles can be thought of as pseudo-disks if one does not have degenerate situations (which one can ensure I am guessing by perturbation or elimination). May 26, 2021 at 2:51