skip to main content
10.1145/1377676.1377696acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
research-article

Helly-type theorems for approximate covering

Published:09 June 2008Publication History

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.

References

  1. N. Amenta. Helly theorems and generalized linear programming. Ph.D. thesis, U.C. Berkeley, 1993. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. N. Amenta. Helly-type theorems and generalized linear programming. Discrete and Computational Geometry, 12:241--261, 1994.Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. H. Bronnimann and M.T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry, 14:463--479, 1995.Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. K.L. Clarckson and K. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete and Computational Geometry, 37:43--58, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle Scholar
  6. 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 ScholarGoogle Scholar
  7. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634--652, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, 85--103, 1972.Google ScholarGoogle Scholar
  9. C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960--981, 1994. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. J. Pach and M. Sharir. Combinatorial Geometry with Algorithmic Applications -- The Alcala Lectures. Alcala (Spain), August 31 - September 5, 2006.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle Scholar
  12. L.A. Santalo. Integral Geometry and Geometric Probability. Cambridge University Press, New York, NY, Second edition, 2004.Google ScholarGoogle Scholar
  13. R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete and Computational Geometry, 6(5):423--424, 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Helly-type theorems for approximate covering

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry
        June 2008
        304 pages
        ISBN:9781605580715
        DOI:10.1145/1377676

        Copyright © 2008 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 9 June 2008

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate625of1,685submissions,37%

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader