4-Holes in point sets Article

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

Overview

abstract

• We consider a variant of a question of Erdos on the number of empty k-gons (k-holes) in a set of n points in the plane, where we allow the k-gons to be non-convex. We show bounds and structural results on maximizing and minimizing the number of general 4-holes, and maximizing the number of non-convex 4-holes. In particular, we show that for n≥9, the maximum number of general 4-holes is (n4); the minimum number of general 4-holes is at least 5/2n 2-Θ(n); and the maximum number of non-convex 4-holes is at least 1/2n3-Θ(n2logn) and at most 1/2n 3-Θ(n2). © 2014 Elsevier B.V.

authors

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

publication date

• 2014-01-01

published in

• Computational Geometry: Theory and Applications  Journal

Research

keywords

• Empty k-gons; Erdos-Szekeres type problems; k-Holes Empty k-gons; Erdos-Szekeres type problems; k-Holes; Minimizing the number of; Point set; Computational geometry; Applications

Identity

Digital Object Identifier (DOI)

• 10.1016/j.comgeo.2013.12.004

Additional Document Info

start page

• 644

end page

• 650

volume

• 47

issue

• 6