×

zbMATH — the first resource for mathematics

Leere konvexe Vielecke in ebenen Punktmengen. (Empty convex polygons in planar point sets). (German) Zbl 0629.52016
Naturwissenschaftliche Fakultät der Technischen Universität Carolo- Wilhelmina Braunschweig. 46 S. (1987).
For any planar n-point set M with no three points collinear, let \(h_ k(M)\) be the number of empty convex k-gons in M (“empty” means that the convex k-gon has no point of M in its interior). Set \(h_ k(n)=\min \{h_ k(M):| M| =n\}\). The author shows that \(h_ 3(n)\geq n^ 2-5n+7\) and \(h_ 4(n)\geq \left( \begin{matrix} n-3\\ 2\end{matrix} \right)\) and that equalities hold for \(3\leq n\leq 9\). Moreover, he also shows that \(h_ 3(10)=58\), \(h_ 4(10)=23\), \(h_ 5(10)=1\), \(h_ 3(11)=75\), \(h_ 4(11)=32\), \(h_ 5(11)=2\), \(94\leq h_ 3(12)\leq 95\), \(42\leq h_ 4(12)\leq 44\), \(3\leq h_ 5(12)\leq 4\) and, for all \(n\geq 13\), \(h_ 3(n)\geq n^ 2- 5n+10,\quad h_ 4(n)\geq \left( \begin{matrix} n-3\\ 2\end{matrix} \right)+6\) and \(h_ 5(n)\geq 3[n/12]\).
Reviewer: J.Daneś

MSC:
52A40 Inequalities and extremum problems involving convexity in convex geometry
52A37 Other problems of combinatorial convexity
52A10 Convex sets in \(2\) dimensions (including convex curves)
52Bxx Polytopes and polyhedra