<p>In the <em>Geometric Hitting Set</em> problem, we are given a set of <span class="math-container">$m$</span> geometric objects and a set of <span class="math-container">$n$</span> points in <span class="math-container">$\mathbb{R}^2$</span>, and we wish to find a small subset of the points that hits all the objects.</p>
<p><em>Geometric Hitting Set</em> has a PTAS running in time <span class="math-container">$mn^{O(1/\epsilon^2)}$</span> for various types of geometric objects, including pseudo-disks and same-height rectangles (<a href="https://link.springer.com/article/10.1007/s00454-010-9285-9" rel="nofollow noreferrer">Mustapha-Ray, 2010</a>).</p>
<p>I am interested in approximation algorithms that achieve a constant-factor approximation, but that run relatively fast, say, <span class="math-container">$O((m+n)^{20})$</span>. For example, for pseudo-disk objects, such algorithms exist (<a href="https://drops.dagstuhl.de/opus/volltexte/2015/4913/" rel="nofollow noreferrer">Bus-Garg-Mustapaha-Ray, 2015</a>).</p>
<p><b>My question:</b> does there exist a comparable algorithm for same-height rectangle objects?</p>

CC BY-SA 4.0
2021-05-24T19:13:16.257Z
How much fast? since for $\epsilon = 1/2$, $m \cdot n^{1/\epsilon^2} \in O((m+n)^4)$ already...
Inuyasha Yagami
CC BY-SA 4.0
2021-05-24T19:24:56.610Z
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
CC BY-SA 4.0
2021-05-24T23:55:24.427Z
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
CC BY-SA 4.0
2021-05-25T09:14:03.320Z
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
CC BY-SA 4.0
2021-05-25T09:24:10.270Z
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
CC BY-SA 4.0
2021-05-26T02:51:24.647Z
@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
CC BY-SA 4.0
2021-06-07T02:16:40.770Z
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](https://doi.org/10.1007/BF02570718), and also see also the discussion [here](https://cstheory.stackexchange.com/questions/182/parameterized-complexity-of-hitting-set-in-finite-vc-dimension)?  Maybe [here](https://doi.org/10.1007/s00454-006-1273-8)? (Random guesses here due to lack of time to check carefully.)
Neal Young
<reference-request><computational-geometry><set-cover>
"Fast" approximation algorithm for geometric hitting set of same-height rectangles
Florent Foucaud
# "Fast" approximation algorithm for geometric hitting set of same-height rectangles

(Asked by: username_0 on 2021-05-24)

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](https://link.springer.com/article/10.1007/s00454-010-9285-9)).

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](https://drops.dagstuhl.de/opus/volltexte/2015/4913/)).

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

**Tags:** reference-request, computational-geometry, set-cover
> **Comments:**
> **username_1**: How much fast? since for $\epsilon = 1/2$, $m \cdot n^{1/\epsilon^2} \in O((m+n)^4)$ already...  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_0**: 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).  
> **username_2**: @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).  
> **username_3**: 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](https://doi.org/10.1007/BF02570718), and also see also the discussion [here](https://cstheory.stackexchange.com/questions/182/parameterized-complexity-of-hitting-set-in-finite-vc-dimension)?  Maybe [here](https://doi.org/10.1007/s00454-006-1273-8)? (Random guesses here due to lack of time to check carefully.)  

---

## 0 answers

