Large convex holes in random point sets Article

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

Overview

abstract

• A convex hole (or empty convex polygon) of a point set P in the plane is a convex polygon with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in the plane. We show that the expected number of vertices of the largest convex hole of a set of n random points chosen independently and uniformly over R is Θ(logn/(loglogn)), regardless of the shape of R. © 2012 Elsevier B.V.

authors

• Balogh J.
• González Aguilar Hernán
• Salazar Anaya Gelasio

publication date

• 2013-01-01

published in

• Computational Geometry: Theory and Applications  Journal

Research

keywords

• Convex hole; Erdős–Szekeres Theorem; Random point set Applications; Computational geometry; Convex hole; Convex polygon; nocv1; Point set; Random point set; Random points; Geometry

Identity

Digital Object Identifier (DOI)

• 10.1016/j.comgeo.2012.11.004

Additional Document Info

start page

• 725

end page

• 733

volume

• 46

issue

• 6