abstract

• We consider a variation of the classical Erd}os-Szekeres problems on the existence and number of convex k-gons and k-holes (empty k-gons) in a set of n points in the plane. Allowing the k-gons to be non-convex, we show bounds and structural results on maximizing and mini- mizing their numbers. Most noteworthy, for any k and sufficiently large n, we give a quadratic lower bound for the number of k-holes, and show that this number is maximized by sets in convex position. We also pro- vide an improved lower bound for the number of convex 6-holes.

authors

• Aichholzer O.
• Fabila-Monroy R.
• González Aguilar Hernán
• Hackl T.
• Heredia M.A.
• Huemer C.
• Urrutia J.
• Valtr P.
• Vogtenhuber B.

publication date

• 2011-01-01

published in

• Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011  Proceedings

keywords

• Large N; Lower bounds; Point set; Computational geometry

start page

end page