On the Expected Complexity of Random Convex Hulls

Details On the Expected Complexity of Random Convex Hulls On the Expected Complexity of Random Convex Hulls

2011-11-22

arxiv.org/abs/1111.5340v1

Computer Science

Computational Geometry

Scientific paper

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(n^{1/3})$, and $O(k \log{n})$ 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 $\Re^d$. 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(\log^{d-1}n)$. 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.

Affiliated with

Also associated with

No associations

Rating

On the Expected Complexity of Random Convex Hulls does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Expected Complexity of Random Convex Hulls, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Expected Complexity of Random Convex Hulls will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375641