## 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 - Dec 1 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