Logo image
Back
Improved Approximation Algorithms for Geometric Set Cover
Journal article   Open access   Peer reviewed

Improved Approximation Algorithms for Geometric Set Cover

Kenneth L. Clarkson and Kasturi Varadarajan
Discrete & computational geometry, Vol.37(1), pp.43-58
01/2007
DOI: 10.1007/s00454-006-1273-8
url
https://doi.org/10.1007/s00454-006-1273-8View
Published (Version of record) Open Access

Abstract

Given a collection S of subsets of some set double-struck U sign, and double-struck M sign ⊂ double-struck U sign, the set cover problem is to find the smallest subcollection C ⊂ S that covers double-struck M sign, that is, double-struck M sign ⊆ ∪(C), where ∪(C) denotes ∪Y∈CY. We assume of course that S covers double-struck M sign. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually double-struck U sign = ℝd. Combining previously known techniques [4], [5], we show that polynomial-time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R ⊂ S and nondecreasing function f(•), there is a decomposition of the complement double-struck U sign\ ∪(R) into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in ℝ3 and for guarding an x-monotone polygonal chain. © 2006 Springer.

Details

Metrics

11 Record Views
138 Times Cited - Web of Science
Logo image