Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is well-known that the expected number of vertices on the convex hull of random set of points in the plane distributed uniformly within a $k$-gon is $O(k\log n)$ and within a smooth shape (e.g. a disk) is $O(n^{1/3})$. These bounds also extend to $\mathbb{R}^d$ with arbitrary $d$, by tacking on a $d-1$ exponent. But, I'm only interested in $\mathbb{R}^2$ for now.

My question is: What is wrong with the following argument for the number of layers in a $k$-gon to be $\Theta(n/\log n)$, taking $k$ as a constant:

In $\mathbb{R}^2$, the number of vertices of $conv(P)$ is $\Theta(\log n)$. After peeling off $i$ layers, the points $P_{i+1}$ enclosed by layer $L_i$ are also independently and uniformly distributed, so their convex hull $conv(P_{i+1})$ should also have $\Theta(\log |P_{i+1}|) = O(\log n)$.

I'm aware of the following result by Dalal:

In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is $\Theta(n^{2/3})$. Additionally, we show that in general the bound is $\Theta(n^{2/(d+1)})$ for points distributed in a $d$-dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full-dimensional shape with a nonempty interior.

I guess my question could also be put more simply as this: Why is the expected number of layers for $k$-gons not $O(n/\log n)$? Why is there a difference in the size of the convex hull between the case when the random points are drawn from a polygon and smooth shapes, but there is no such difference in the expected number of layers, based on Dalal's result (unless I misunderstand his claim)? An intuitive reason should do, but a formal argument or a pointer to one will be great!

share|improve this question
1  
But $P_1$ is not uniformly distributed in a square; it's uniformly distributed in $conv(P)$, which has $\Theta(\log n)$ sides in expectation. So the right back-of-the-envelope estimate for the complexity of the convex hull of $P_1$ is $\Theta(\log^2 n)$. More generally, deeper layers are "rounder", and boundary effects matter less. –  JeffE May 19 '12 at 19:44
    
@JeffE: Thanks a million! That certainly makes a great deal of sense to me now. Dalal's argument is something like this: any convex body that contains a disk (circle) should have no fewer layers than the disk, and thus, since disks have $\Theta(n^{2/3})$ layers, this bound should also hold for them in expectation. Going back to your back-of-the-envelope estimate, we should then expect the $i$-th layer $P_i$ to have have expected complexity $\Theta(\log^{i+1} n)$, right? –  rrufai May 19 '12 at 21:22
    
@JeffE: In other words, the number of layers we seek will be the $k$ for which the expression $n - \sum_{i=0}^k{c_i\log^{i+1}n}$ (where $c_i$ are constants) vanishes? –  rrufai May 19 '12 at 22:10
    
Well, that's just a back of the envelope estimate. It might be good for intuition, but I wouldn't trust it to give a precise bound, especially after several iterations. –  JeffE May 20 '12 at 4:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.