0
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ How much fast? since for $\epsilon = 1/2$, $m \cdot n^{1/\epsilon^2} \in O((m+n)^4)$ already... $\endgroup$
    – Inuyasha Yagami
    May 24, 2021 at 19:13
  • $\begingroup$ 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. $\endgroup$
    – Florent Foucaud
    May 24, 2021 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    May 24, 2021 at 23:55
  • $\begingroup$ 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. $\endgroup$
    – Florent Foucaud
    May 25, 2021 at 9:14
  • 1
    $\begingroup$ @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). $\endgroup$
    – Chandra Chekuri
    May 26, 2021 at 2:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy