کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650612 | 1632449 | 2006 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Berge's theorem, fractional Helly, and art galleries Berge's theorem, fractional Helly, and art galleries](/preview/png/4650612.png)
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 (d+1)(d+1)-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 (p,3)(p,3)-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 (p,q)(p,q)-theorem of this kind holds with p⩾2q-1p⩾2q-1.
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2303–2313