6
$\begingroup$

We know $n>2$ and worst case its a triangle, best case the points all lie on a circle. Can we generalize to higher dimensions? What's the probability that the size of the convex hull of $n$ points randomly selected in a circle is $k$?

$\endgroup$

2 Answers 2

8
$\begingroup$

The expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk, is $O(n^{\frac{1}{3}})$.

The result goes back to the 1960's. A nice proof is in Har-Peled, "On the expected complexity of random convex hulls" (1997), from which the above sentence is quoted. (arXiv version abstract.)

$\endgroup$
0
$\begingroup$

Amazing result! Some code for the computation-minded.

import numpy as np
from scipy.spatial import ConvexHull

def countVertex(n):
    points = np.random.random((n, 2))
    hull = ConvexHull(points)
    return hull.nsimplex

def testN(n, nTrial=20):
    return np.array( [ countVertex(n) for i in range(nTrial) ])

def testAllN(n_list):
    nTrial = 20
    nN = len(n_list)
    result = np.zeros((nN, nTrial))
    for i,n in enumerate(n_list):
        result[i,:] = testN(n, nTrial)
    np.savetxt('result.dat', result)

testAllN(range(5,100,5))

A sample result is below. The fitting line is $2.92 x^{0.318}$. sample

$\endgroup$
1
  • $\begingroup$ The code samples random points from a unit square instead of a unit disk, but the 1/3 scaling seems to apply as well. $\endgroup$
    – Taozi
    Oct 14, 2021 at 19:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .