Article ID Journal Published Year Pages File Type
414776 Computational Geometry 2013 9 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,