Exact algorithms and APX-hardness results for geometric set cover

Timothy M. Chan, Elyot Grant

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
StatePublished - Dec 1 2011
Externally publishedYes
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: Aug 10 2011Aug 12 2011

Other

Other23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Country/TerritoryCanada
CityToronto, ON
Period8/10/118/12/11

ASJC Scopus subject areas

  • Computational Mathematics
  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Exact algorithms and APX-hardness results for geometric set cover'. Together they form a unique fingerprint.

Cite this