On k-gons and k-holes in point sets Article

•  
• Overview
•  
• Research
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

abstract

• We consider a variation of the classical Erdos-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 minimizing 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. © 2014 Elsevier B.V. All rights reserved.

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

• 2015-01-01

published in

• Computational Geometry: Theory and Applications  Journal

Research

keywords

• Empty k-gons; Erdos-Szekeres type problems; k-Gons; k-Holes Empty k-gons; Erdos-Szekeres type problems; Large N; Lower bounds; Point set; Computational geometry

Identity

Digital Object Identifier (DOI)

• 10.1016/j.comgeo.2014.12.007

Additional Document Info

start page

• 528

end page

• 537

volume

• 48

issue

• 7