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!

  • 3
    $\begingroup$ 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. $\endgroup$ – JeffE May 19 '12 at 19:44
  • $\begingroup$ @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? $\endgroup$ – rrufai May 19 '12 at 21:22
  • $\begingroup$ @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? $\endgroup$ – rrufai May 19 '12 at 22:10
  • $\begingroup$ 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. $\endgroup$ – JeffE May 20 '12 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.