×

zbMATH — the first resource for mathematics

On empty convex polygons in a planar point set. (English) Zbl 1088.52500
Summary: Let \(P\) be a set of \(n\) points in general position in the plane. Let \(X_{k}(P)\) denote the number of empty convex \(k\)-gons determined by \(P\).
We derive, using elementary proof techniques, several equalities and inequalities involving the quantities \(X_{k}(P)\) and several related quantities. Most of these equalities and inequalities are new, except for a few that have been proved earlier using a considerably more complex machinery from matroid and polytope theory, and algebraic topology. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.

MSC:
52A10 Convex sets in \(2\) dimensions (including convex curves)
52A40 Inequalities and extremum problems involving convexity in convex geometry
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahrens, C.; Gordon, G.; McMahon, E.W., Convexity and the beta invariant, Discrete comput. geom., 22, 411-424, (1999) · Zbl 0966.52006
[2] I. Bárány, personal communication.
[3] Bárány, I.; Füredi, Z., Empty simplices in Euclidean space, Canad. math. bull., 30, 436-445, (1987) · Zbl 0639.52006
[4] I. Bárány, G. Károlyi, Problems and results around the Erdős-Szekeres convex polygon theorem, in: J. Akiyama, M. Kano, M. Urabe (Eds.), Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG) 2000, Tokyo, Japan, Lecture Notes in Computer Science, vol. 2098, Springer, Berlin, (2001), pp. 91-105. · Zbl 0998.52004
[5] Bárány, I.; Valtr, P., Planar point sets with a small number of empty convex polygons, Studia. sci. math. hungar., 41, 243-266, (2004) · Zbl 1075.52008
[6] P. Brass, On point sets without \(k\) collinear points, in: A. Bezdek (Ed.), Discrete Geometry—in Honor of W. Kuperberg’s 65th Birthday, Marcel Dekker, 2003, pp. 185-192. · Zbl 1053.52021
[7] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, Berlin, New York, in press.
[8] Dumitrescu, A., Planar sets with few empty convex polygons, Studia. sci. math. hungar., 36, 93-109, (2000) · Zbl 0980.52007
[9] Edelman, P.H.; Jamison, R., The theory of convex geometries, Geom. dedicata, 19, 247-270, (1987) · Zbl 0577.52001
[10] Edelman, P.H.; Reiner, V., Counting the interior of a point configuration, Discrete comput. geom., 23, 1-13, (2000) · Zbl 0953.52007
[11] Edelman, P.H.; Reiner, V.; Welker, V., Convex, acyclic, and free sets of an oriented matroid, Discrete comput. geom., 27, 99-116, (2002) · Zbl 0997.52016
[12] Erdős, P., Research problem 36, Period. math. hungar., 15, 101-103, (1984)
[13] Erdős, P.; Purdy, G., Extremal problems in combinatorial geometry, (), 809-874 · Zbl 0852.52009
[14] Füredi, Z.; Palasti, I., Arrangements of lines with large number of triangles, Proc. amer. math. soc., 92, 561-566, (1984) · Zbl 0521.51003
[15] Harborth, H., Konvexe Fünfecke in ebenen punktmengen, Elem. math., 33, 116-118, (1978) · Zbl 0397.52005
[16] F. Hirzebruch, Singularities of algebraic surfaces and characteristic numbers, in: Proceedings of the Lefschetz Centennial Conference, Part I, Mexico City, 1984, AMS Contemporary Mathematics Series, vol. 58, American Mathematical Society, Providence, RI, 1986, pp. 141-150.
[17] Horton, J.D., Sets with no empty convex 7-gons, Canad. math. bull., 26, 482-484, (1983) · Zbl 0521.52010
[18] Ismailescu, D., Restricted point configurations with many collinear \(k\)-tuplets, Discrete comput. geom., 28, 571-575, (2002) · Zbl 1018.52012
[19] Katchalski, M.; Meir, A., On empty triangles determined by points in the plane, Acta math. hungar., 51, 323-328, (1988) · Zbl 0655.52007
[20] Klain, D., An Euler relation for valuations of polytopes, Adv. math., 147, 1-34, (1999) · Zbl 0944.52007
[21] Matoušek, J.; Nešetřil, J., Invitation to discrete mathematics, (1998), Clarendon Press Oxford · Zbl 0901.05001
[22] Overmars, M., Finding sets of points without empty convex 6-gons, Discrete comput. geom., 29, 153-158, (2003) · Zbl 1019.52010
[23] Overmars, M.; Scholten, B.; Vincent, I., Sets without empty convex 6-gons, Bull. European assoc. theor. comput. sci., 37, 160-168, (1989) · Zbl 1023.68686
[24] Szemerédi, E.; Trotter, W.T., Extremal problems in discrete geometry, Combinatorica, 3, 381-392, (1983) · Zbl 0541.05012
[25] Valtr, P., On the minimum number of empty polygons in planar point sets, Studia. sci. math. hungar., 30, 155-163, (1995) · Zbl 0867.52004
[26] P. Valtr, personal communication.
[27] Ziegler, G.M., Lectures on polytopes, (1995), Springer Berlin, New York · Zbl 0823.52002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.