0

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?

Florent Foucaud
  • 2,153
  • 12
  • 27
  • How much fast? since for $\epsilon = 1/2$, $m \cdot n^{1/\epsilon^2} \in O((m+n)^4)$ already... – Inuyasha Yagami May 24 '21 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. – Florent Foucaud May 24 '21 at 19:24
  • 1
    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 https://dl.acm.org/doi/abs/10.5555/3381089.3381151 and pointers and other recent work by Timothy Chan and others. – Chandra Chekuri May 24 '21 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. – Florent Foucaud May 25 '21 at 09:14
  • Actually, I get confused about what is a pseudo-disk or not: I thought pseudo-disks are objects such that the boundaries of any two objects can intersect at most twice. But in the abstract of this paper by Mustapha, Raman and Ray (https://hal.archives-ouvertes.fr/hal-01188991/document) claims that unit height rectangles are pseudo-disks (while their boundaries may intersect in infinitely many points). – Florent Foucaud May 25 '21 at 09:24
  • 1
    @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). – Chandra Chekuri May 26 '21 at 02:51
  • Do the O(1)-approximation algorithms for set systems whose duals have constant VC dimension apply? I think there are greedy-ish algorithms based on epsilon-nets. I think there's a 1995 paper by Bronniman, and also see also the discussion here? Maybe here? (Random guesses here due to lack of time to check carefully.) – Neal Young Jun 07 '21 at 02:16

0 Answers0