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
    • the average value of H,
    • the standard deviation
    • the skewness and excess kurtosis (calculated from these formulae)
    for each distribution of points.
  • 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 of points.
nUniform SquareUniform CircleUniform Eq. TriangleGaussian
meanstdevskewkurtmeanstdevskewkurtmeanstdevskewkurtmeanstdevskewkurt
105.9640.9870.162-0.1116.1150.9780.168-0.1015.6581.0440.132-0.0824.7860.9080.3370.069
207.7541.3050.183-0.0378.2661.2670.208-0.0177.0921.3480.1810.05.4761.0530.3510.114
5010.1591.6810.1630.01611.7941.6060.2110.0448.9551.6770.185-0.00206.3271.2070.3590.136
10011.9891.950.1530.01615.1741.8560.1710.01410.3591.8870.1730.0396.9141.3070.3420.12
20013.8292.1820.1470.01719.3562.1260.1730.03511.7472.0830.1590.027.4651.3960.3390.087
50016.2592.4750.147-0.001026.5472.5280.138-0.002013.5912.3140.1660.0268.1551.5020.3210.082
100018.1212.6750.1370.02933.5812.8470.1420.01314.9822.4850.1640.0448.6221.5720.3360.128
200019.9712.8530.1460.04342.423.2060.126-0.003016.3452.6240.150.0219.0891.6310.3170.069
500022.43.0920.1310.05657.7163.7520.0940.006018.1752.8130.1520.0279.6741.7120.3080.097
1000024.2583.2580.1260.002072.7944.2190.0880.008019.582.9480.1420.05110.1081.760.3110.151
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!

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.