Exact algorithms and APX-hardness results for geometric packing and covering problems

Timothy M. Chan, Elyot Grant

Research output: Contribution to journalArticle

Abstract

We study several geometric set cover and set packing problems involving configurations of points and geometric objects in Euclidean space. We show that it is APX-hard to compute a minimum cover of a set of points in the plane by a family of axis-aligned fat rectangles, even when each rectangle is an ϵ-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, fat semi-infinite wedges, 3-dimensional unit balls, and axis-aligned cubes, as well as some related hitting set problems. We also prove the APX-hardness of a related family of discrete set packing 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 geometric 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. We give similar algorithms for several related hitting set and discrete packing problems.

Original languageEnglish (US)
Pages (from-to)112-124
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume47
Issue number2
DOIs
StatePublished - Feb 1 2014
Externally publishedYes

Keywords

  • APX-hardness
  • Dynamic programming
  • Geometric hitting set
  • Geometric packing
  • Geometric set cover

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Exact algorithms and APX-hardness results for geometric packing and covering problems'. Together they form a unique fingerprint.

  • Cite this