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.

n	Uniform Square				Uniform Circle				Uniform Eq. Triangle				Gaussian
	mean	stdev	skew	kurt	mean	stdev	skew	kurt	mean	stdev	skew	kurt	mean	stdev	skew	kurt
10	5.964	0.987	0.162	-0.111	6.115	0.978	0.168	-0.101	5.658	1.044	0.132	-0.082	4.786	0.908	0.337	0.069
20	7.754	1.305	0.183	-0.037	8.266	1.267	0.208	-0.017	7.092	1.348	0.181	0.0	5.476	1.053	0.351	0.114
50	10.159	1.681	0.163	0.016	11.794	1.606	0.211	0.044	8.955	1.677	0.185	-0.0020	6.327	1.207	0.359	0.136
100	11.989	1.95	0.153	0.016	15.174	1.856	0.171	0.014	10.359	1.887	0.173	0.039	6.914	1.307	0.342	0.12
200	13.829	2.182	0.147	0.017	19.356	2.126	0.173	0.035	11.747	2.083	0.159	0.02	7.465	1.396	0.339	0.087
500	16.259	2.475	0.147	-0.0010	26.547	2.528	0.138	-0.0020	13.591	2.314	0.166	0.026	8.155	1.502	0.321	0.082
1000	18.121	2.675	0.137	0.029	33.581	2.847	0.142	0.013	14.982	2.485	0.164	0.044	8.622	1.572	0.336	0.128
2000	19.971	2.853	0.146	0.043	42.42	3.206	0.126	-0.0030	16.345	2.624	0.15	0.021	9.089	1.631	0.317	0.069
5000	22.4	3.092	0.131	0.056	57.716	3.752	0.094	0.0060	18.175	2.813	0.152	0.027	9.674	1.712	0.308	0.097
10000	24.258	3.258	0.126	0.0020	72.794	4.219	0.088	0.0080	19.58	2.948	0.142	0.051	10.108	1.76	0.311	0.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.