ABSTRACT
Let F ∪ {U} be a collection of convex sets in Rd such that F covers U. We show that if the elements of F and U have comparable size, in the sense that each contains a ball of radius r and is contained in a ball of radius R for some fixed r and R, then for any ε > 0 there exists Hε ⊂ F, whose size |Hε| is polynomial in 1/ε and independent of |F|, that covers U except for a volume of at most ε. The size of the smallest such subset depends on the geometry of the elements of F; specifically, we prove that it is O(1/ε) when F consists of axis-parallel unit squares in the plane and Õ(ε1--d/2) when F consists of unit balls in Rd (here, Õ(n) means O(n log n) for some constant), and that these bounds are, in the worst-case, tight up to the logarithmic factors.
We extend these results to surface-to-surface visibility in 3 dimensions: if a collection F of disjoint unit balls occludes visibility between two balls then a subset of F of size Õ(ε--7/2) blocks visibility along all but a set of lines of measure ε.
Finally, for each of the above situations we give an algorithm that takes F and U as input and outputs in time O(|F|*|Hε|) either a point in U not covered by F or a subset Hε covering U up to a measure ε, with |Hε| satisfying the above bounds.
- N. Amenta. Helly theorems and generalized linear programming. Ph.D. thesis, U.C. Berkeley, 1993. Google ScholarDigital Library
- N. Amenta. Helly-type theorems and generalized linear programming. Discrete and Computational Geometry, 12:241--261, 1994.Google ScholarDigital Library
- H. Bronnimann and M.T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry, 14:463--479, 1995.Google ScholarDigital Library
- K.L. Clarckson and K. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete and Computational Geometry, 37:43--58, 2007. Google ScholarDigital Library
- L. Danzer, B. Grünbaum and V. Klee. Helly's theorem and its relatives. V. Klee editor, Convexity, Proc. of Symposia in Pure Math, 101--180, 1963.Google Scholar
- J. Eckhoff. Helly, Radon and Carathéodory type theorems. In J.E. Goodman and J. O'Rourke, editors, Handbook of Convex Geometry, 389--448, 1993.Google Scholar
- U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998. Google ScholarDigital Library
- R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, 85--103, 1972.Google Scholar
- C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960--981, 1994. Google ScholarDigital Library
- J. Pach and M. Sharir. Combinatorial Geometry with Algorithmic Applications -- The Alcala Lectures. Alcala (Spain), August 31 - September 5, 2006.Google Scholar
- J. Demouth, O. Devillers, M. Glisse and X. Goaoc. Helly-type theorems for approximate covering. Research Report no 6342, INRIA, Oct. 2007. Available on http://hal.inria.fr/inria-00179277/fr/.Google Scholar
- L.A. Santalo. Integral Geometry and Geometric Probability. Cambridge University Press, New York, NY, Second edition, 2004.Google Scholar
- R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete and Computational Geometry, 6(5):423--424, 1991. Google ScholarDigital Library
- M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In STACS '92: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 569--579, 1992. Google ScholarDigital Library
- R. Wenger. Helly-type theorems and geometric transversals. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete & Computation Geometry, 2nd edition, 73--96, 2004. Google ScholarDigital Library
Index Terms
Helly-type theorems for approximate covering
Recommendations
Helly-Type Theorems for Approximate Covering
Let źź{U} be a collection of convex sets in źd such that ź covers U. We prove that if the elements of ź and U have comparable size, then a small subset of ź suffices to cover most of the volume of U; we analyze how small this subset can be depending on ...
Tolerance in Helly-Type Theorems
In this paper we introduce the notion of tolerance in connection with Helly-type theorems and prove, using the Erdźs---Gallai theorem, that any Helly-type theorem can be generalized by relaxing the assumptions and conclusion, allowing a bounded number ...
A Mélange of Diameter Helly-Type Theorems
A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in $\mathbb{R}^d$ given some information on the diameter of the intersection of all sufficiently small subfamilies. We prove ...
Comments