On the Expected Complexity of Random Convex Hulls
Home Bookmarks Papers Blog

On the Expected Complexity of Random Convex Hulls

Sariel Har-Peled


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). Applying the same technique to the case where the points are chosen from a convex polygon with k sides, is O( k log n). 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( n1/3 + (n µ(D))1/2) , where µ(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. Implying that this bound holds also for those cases.

Those bounds are known \cite bkst-anmsv-78 , but we believe the new proof is simpler.

PDF, Postscript.

Technical Report 330/98, School Math. Sci., Tel-Aviv Univ., Tel-Aviv, Israel, 1998.


Last modified: Tue Nov 22 13:49:43 CST 2011