Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414776 | Computational Geometry | 2013 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
József Balogh, Hernán González-Aguilar, Gelasio Salazar,