On the Expected Complexity of Random Convex Hulls

Download PDF

In this paper we present several results on the expected complexity of a convex hull of n points chosen uniformly and independently from a convex shape.
(i) We show that the expected number of vertices of the convex hull of n points, chosen uniformly and independently from a disk is O(n1/3), and O(klogn) for the case a convex polygon with k sides. Those results are well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that the elementary proof given here are simpler and more intuitive.
(ii) Let $\D$ be a set of directions in the plane, we define a generalized notion of convexity induced by $\D$, which extends both rectilinear convexity and standard convexity.
We prove that the expected complexity of the $\D$-convex hull of a set of n points, chosen uniformly and independently from a disk, is $O(n^{1/3} + \sqrt{n\alpha(\D)})$, where $\alpha(\D)$ is the largest angle between two consecutive vectors in $\D$. This result extends the known bounds for the cases of rectilinear and standard convexity.
(iii) Let $\B$ be an axis parallel hypercube in Rd. We prove that the expected number of points on the boundary of the quadrant hull of a set S of n points, chosen uniformly and independently from $\B$ is O(logd−1n). Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in S, and is also larger than the number of points of S that are vertices of the convex hull of S.
Those bounds are known \cite{bkst-anmsv-78}, but we believe the new proof is simpler.