# Approximation ratio for covering n points in d dimensions

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 .

• A constant factor should follow from VC-dimension arguments. I assume you'd want a precise constant ? – Suresh Venkat Sep 19 '12 at 19:49
• Yes , I am looking for a precise value. – Shalabh Vidyarthi Sep 20 '12 at 14:22
• @SureshVenkat Can you elaborate? I'm only aware of the log(OPT) approximation factor that would come automatically from VC-dimension arguments. – James King Sep 22 '12 at 1:16
• 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 Sep 23 '12 at 4:13