×

Berge’s theorem, fractional Helly, and art galleries. (English) Zbl 1103.52003

Summary: 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\))-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\))-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\))-theorem of this kind holds with \(p\geqslant 2q-1\).

MSC:

52A35 Helly-type theorems and geometric transversal theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Kalai, G., Bounding the piercing number, Discrete Comput. Geom., 13, 245-256 (1995) · Zbl 0826.52006
[2] Alon, N.; Kalai, G.; Matoušek, J.; Meshulam, R., Transversal numbers for hypergraphs arising in geometry, Adv. Appl. Math., 29, 79-101 (2001) · Zbl 1027.52003
[3] Alon, N.; Kleitman, D., Piercing convex sets and the Hadwiger Debrunner \((p, q)\)-problem, Adv. Math., 96, 1, 103-112 (1992) · Zbl 0768.52001
[4] Aronov, B.; Chazelle, B.; Edelsbrunner, H.; Guibas, L. J.; Sharir, M.; Wenger, R., Points and triangles in the plane and halving planes in space, Discrete Comput. Geom., 6, 435-442 (1991) · Zbl 0764.68057
[5] Bárány, I., A generalization of Carathéodory’s theorem, Discrete Math., 40, 141-152 (1982) · Zbl 0492.52005
[6] Berge, C., Sur une propriété combinatoire des ensembles convexes, C. R. Acad. Sci. Paris, 248, 2698-2699 (1959), (in French) · Zbl 0092.15202
[7] C. Berge, A. Ghouila-Houri, Programmes, jeux et réseaux de transport, Dunod, Paris, 1962, viii \(+\); C. Berge, A. Ghouila-Houri, Programmes, jeux et réseaux de transport, Dunod, Paris, 1962, viii \(+\)
[8] Breen, M., Starshaped unions and nonempty intersections of convex sets in \(R^d\), Proc. AMS, 108, 817-820 (1990) · Zbl 0691.52006
[9] Eckhoff, J., Helly, Radon and Carathéodory-type theorems, (Gruber, P. M.; Wills, J. M., Handbook of Convex Geometry (1993), North-Holland: North-Holland Amsterdam) · Zbl 0791.52009
[10] Erdős, P.; Simonovits, M., Supersaturated graphs and hypergraphs, Combinatorica, 3, 181-192 (1983) · Zbl 0529.05027
[11] Hadwiger, H.; Debrunner, H., Über eine Variant zum Hellyschen Satz, Archiv Math., 8, 309-313 (1957) · Zbl 0080.15404
[12] Kalai, G., Intersection patterns for convex sets, Israel J. Math., 48, 161-174 (1984) · Zbl 0557.52005
[13] Kalai, G.; Matoušek, J., Guarding galleries where every point sees a large area, Israel J. Math., 101, 125-140 (1997) · Zbl 0953.68137
[14] Katchalski, M.; Liu, A., A problem of geometry in \(R^n\), Proc. Amer. Math. Soc., 75, 284-288 (1979) · Zbl 0418.52013
[15] Krasnosel’skiιˇ, M. A., On a condition of starshapedness, Mat. Sbornik, 19, 309-310 (1946), (in Russian)
[16] Matoušek, J., Lectures on Discrete Geometry (2002), Springer: Springer New York · Zbl 0999.52006
[17] Valtr, P., Guarding galleries where no point sees a small area, Israel J. Math., 104, 1-16 (1998) · Zbl 1045.52500
[18] Valtr, P., On galleries with no bad points, Discrete Comput. Geom., 21, 193-200 (1999) · Zbl 0927.52010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.