# Distance between point and convex hull in high dimensions

I am trying to develop an intuition for the properties of the convex hull of a set of points in high ($$d>20$$) dimensions.

Consider a set of $$n$$ data points which are iid distributed according to some simple distribution (e.g. uniform hypercube, multivariate normal with mean $$\mathbf{0}$$ and identity covariance matrix $$\mathbf{I}_d$$, or similar). Now suppose we draw an $$n+1$$'th data point $$\mathbf{x}$$ from that same distribution. What can we say about the relationship between $$\mathbf{x}$$ and the convex hull of the first $$n$$ points?

My expectation$$^1$$ is that as dimensionality increases, the distance between $$\mathbf{x}$$ and the convex hull should grow for fixed $$n$$. I also expect the volume of the convex hull to, in some sense, shrink relative to the volume of the domain or something similar.

To make this more concrete, I would like some expression (or bound) on the expected distance between $$\mathbf{x}$$ and the convex hull for some simple data distribution as a function of $$n$$ and $$d$$.

Does such an example exist (either analytic or numeric) which could aid with my intuition?

Disclaimer: this is not my area of expertise, so even simple examples or half-answers would be very helpful.

$$^1$$ Inspired by section 2.5 of The Elements of Statistical Learning where the authors demonstrate the curse of dimensionality (e.g. points tend to be further apart as dimensions increase, side-length of the subcube needed to capture a fraction r of the volume of the data increases with dimension).

• Perhaps the easiest upper bound on the expectation you can find is $E( \| X_{n+1} - \overline{X}_n\|_2 )$. Is this helpful? Commented Jan 17, 2022 at 18:53
• Let $y^{(i)}$, $i=1,\dots, n$, be the first $n$ data points, and let $x$ be the subsequent data point. Draw each data point uniformly from a $d$ dimensional unit hypercube $[0,1]^d$. The probability that $x_j \geq \max_i y_j^{(i)}+1/2$ is $\int_{1/2}^1 dx_j (x_j-1/2)^n = \frac{1}{2^{n+1} (n+1)}$. The squared distance from $x$ to the convex hull of the $y$'s is at least $\sum_j \max\left(0,x_j - \max_i y_j^{(i)}\right)^2$. Each term of the sum is $>1/4$ with probability $\frac{1}{2^{n+1} (n+1)}$, so the sum has expectation $> \frac{d}{2^{n+3}(n+1)}$.
– Yly
Commented Jan 18, 2022 at 8:28
• @JoseAvilez This is along the lines of what I mentioned in the footnote but I would like to understand something about the nature of the convex hull rather than the fact that data becomes sparse and on the edge. Commented Jan 18, 2022 at 14:06
• @Yly this seems promising. If you could flesh this out into a complete answer it would be appreciated. I have only 20 hours left to award the bounty! Commented Jan 18, 2022 at 14:08