How many points on the convex hull?
The convex hull of a set of points on the plane is, simply, the shape you'd get if you
stretched an elastic band around them. There is a more detailed explanation and
and an applet to help visualize the convex hull elsewhere on this site.
The number of points H on the convex hull depends on the number N and arrangement of the original points.
If we scatter points randomly on the plane, we can talk about the expected number of points
on the hull. This will depend on exactly how the original points are scattered.
The table below shows information about
the likely values of H for various values of N, for various distributions of points. Some explanation is in order.
- For each value of N, I randomly selected N points according to some distribution. Then I calculated the number of points H on the convex hull.
- In fact, I did this 100,000 times for each value of N.
- The table below shows
for each distribution of points.
- the average value of H,
- the standard deviation
- the skewness and excess kurtosis (calculated from these formulae)
- The four distributions of points are :
- Uniform square : the N points are uniformly distributed in a square (side length 2).
- Uniform circle : the N points are uniformly distributed in a circle (radius 1).
- Uniform triangle : the N points are uniformly distributed in an equilateral triangle.
- Gaussian : the N points are distributed on the plane according to a gaussian distribution.
- This is more useful than it appears at first. The results for the square apply to any
parallelogram, those for the circle to any ellipse, and those for the equilateral triangle
to any triangle at all. Similarly, for the gaussian distribution, my covariance matrix
is the identity, but the same results should apply for any bivariate gaussian distribution
As I mentioned, the above values are calculated from a sample of 100000 convex hulls for each value of N and distribution
of points. If anyone knows the theoretical "correct" values, please let me know!
|n||Uniform Square||Uniform Circle||Uniform Eq. Triangle||Gaussian|
Update! Thanks to Mike Beuoy for pointing out that I previously had the column hedings of the above table the wrong way round! This is now fixed!
Also, the theoretical correct values, at least for the means and variances, are known. For example, this Biometrika article (also available through JSTOR) gives integrals which give the mean and variance for the gaussian and uniform circle cases. Other articles give results for arbitrary polytopes - this would certainly cover the square and the triangle! Unfortunately, the integrals are very messy to work out.