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.
publication date
published in
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)
Additional Document Info
start page
end page
volume
issue