About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SCG 2009
Conference paper
On the set multi-cover problem in geometric settings
Abstract
We consider the set multi-cover problem in geometric settings. Givena set of points P and a collection of geometric shapes (or sets) ℱ, we wish to find a minimum cardinality subset of ℱ such that each point p ∈ P is covered by (contained in) at least d(p) sets. Here d(p) is an integer demand (requirement) for p. When the demands d(p) = 1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this paper, we show that similar improvements can be obtained for the multi-cover problem as well. In particular, we obtain an O (log opt) approximation for set systems of bounded VC- dimension, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes. © 2009 ACM.