Abstract
We study several geometric set cover problems in which the goal is to compute a minimum cover of a given set of points in Euclidean space by a family of geometric objects. We give a short proof that this problem is APX-hard when the objects are axis-aligned fat rectangles, even when each rectangle is an o-perturbed copy of a single unit square. We extend this result to several other classes of objects including almost-circular ellipses, axis-aligned slabs, downward shadows of line segments, downward shadows of graphs of cubic functions, 3-dimensional unit balls, and axis-aligned cubes, as well as some related hitting set problems. Our hardness results are all proven by encoding a highly structured minimum vertex cover problem which we believe may be of independent interest. In contrast, we give a polynomial-time dynamic programming algorithm for 2-dimensional set cover where the objects are pseudodisks containing the origin or are downward shadows of pairwise 2-intersecting x-monotone curves. Our algorithm extends to the weighted case where a minimum-cost cover is required.
Original language | English (US) |
---|---|
State | Published - 2011 |
Externally published | Yes |
Event | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Duration: Aug 10 2011 → Aug 12 2011 |
Other
Other | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 |
---|---|
Country/Territory | Canada |
City | Toronto, ON |
Period | 8/10/11 → 8/12/11 |
ASJC Scopus subject areas
- Computational Mathematics
- Geometry and Topology