<p>What is best known approximation ratio for the following problem :</p>

<p>Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a point , if the point lies on the line .</p>

CC BY-SA 3.0
2012-09-19T19:49:10.120Z
A constant factor should follow from VC-dimension arguments. I assume you'd want a precise constant ?
Suresh Venkat
CC BY-SA 3.0
2012-09-20T14:22:45.090Z
Yes , I am looking for a precise value.
Shalabh Vidyarthi
CC BY-SA 3.0
2012-09-22T01:16:53.823Z
@SureshVenkat Can you elaborate?  I'm only aware of the log(OPT) approximation factor that would come automatically from VC-dimension arguments.
James King
CC BY-SA 3.0
2012-09-23T04:13:09.513Z
Each point is in exactly $d$ axis-parallel lines so this is a special case of set cover where an element is in at most $d$ sets. One can get a $d$-approximation via LP rounding but perhaps one can do better using the geometric structure?
Chandra Chekuri
<cg.comp-geom><approximation-algorithms><set-cover>
Approximation ratio for covering n points in d dimensions
Shalabh Vidyarthi
# Approximation ratio for covering n points in d dimensions

(Asked by: username_0 on 2012-09-19)

What is best known approximation ratio for the following problem :

Given n points in d dimensions , what is the minimum number of axis parallel lines needed to cover them . A line is said to cover a point , if the point lies on the line .

**Tags:** cg.comp-geom, approximation-algorithms, set-cover

> **Comments:**
> **username_1**: A constant factor should follow from VC-dimension arguments. I assume you'd want a precise constant ?  
> **username_0**: Yes , I am looking for a precise value.  
> **username_2**: @SureshVenkat Can you elaborate?  I'm only aware of the log(OPT) approximation factor that would come automatically from VC-dimension arguments.  
> **username_3**: Each point is in exactly $d$ axis-parallel lines so this is a special case of set cover where an element is in at most $d$ sets. One can get a $d$-approximation via LP rounding but perhaps one can do better using the geometric structure?  

---

## 0 answers

