Back to Search
Start Over
Berge's theorem, fractional Helly, and art galleries
- Source :
-
Discrete Mathematics . Oct2006, Vol. 306 Issue 19/20, p2303-2313. 11p. - Publication Year :
- 2006
-
Abstract
- Abstract: In one of his early papers Claude Berge proved a Helly-type theorem, which replaces the usual “nonempty intersection” condition with a “convex union” condition. Inspired by this we prove a fractional Helly-type result, where we assume that many -tuples of a family of convex sets have a star-shaped union, and the conclusion is that many of the sets have a common point. We also investigate somewhat related art-gallery problems. In particular, we prove a -theorem for guarding planar art galleries with a bounded number of holes, completing a result of Kalai and Matoušek, who obtained such a result for galleries without holes. On the other hand, we show that if the number of holes is unbounded, then no -theorem of this kind holds with . [Copyright &y& Elsevier]
- Subjects :
- *MATHEMATICS
*INTEGRAL theorems
*ART museums
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 306
- Issue :
- 19/20
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 22607017
- Full Text :
- https://doi.org/10.1016/j.disc.2005.12.028