What is the expected convex depth of a set of $m$ randomly chosen points in the unit square?

Definition. Let $X$ be a set of points in $\mathbb{R}^2$. Then the vertex sequence of $X$ is defined by

1. $X_{0}=X$, and
2. $X_{i+1}=\left\{x\in \operatorname{Conv}(X_{i}): x \notin \operatorname{Conv}(X_{i}\setminus\{x\})\right\}$.

The convex depth of $X$ is the smallest $k\in \mathbb{N}$ such that $X_{k}$ is empty.

Here is an example where $|X|=30$.

My question is,

What is the expected convex depth of a set of $m$ randomly chosen points in the unit square?

The answer should be a function of $m$. I have simulated some data for this, pictured below, where the $x$- axis is $m$ and $y$- axis is the mean convex depth. It looks $\sqrt{m}$ish (or maybe something closer to $m^{3/2}$, as suggested by lhf's link in the comments). I'm not sure how to prove it, though.

.

Solution 1:

It's $m^{2/3}$. See Ketan Dalal, Counting the onion, Random Struct. Alg., 24 (2004), 155–165, doi:10.1002/rsa.10114.

Solution 2:

If you take that the average minimum distance between two points for uniformly distributed (random) N points in a unit circle is approximated for large N by: $\langle{d}\rangle=\frac{1}{\sqrt{2}N}$

You can imagine then a unit circle with some rather large N number of points and $m_\delta$ number of vertex sequences. Suppose we add a concentric annulus of exactly $\langle{d}\rangle$ width around the unit circle so we have increased the number of points by $N_\delta=pA$. Where $p=\frac{N}{\pi}$ is the point area density and A is the area of the annulus. So $N_\delta = (\sqrt{2} + \frac{1}{2N})/\pi$

Since we have chosen an annulus width of exactly that of the min average distance between points it's easy to see that we would get two new convex vertex sequence on average within this new annulus. You can understand this by imagining that there are a lot of points within this very thin annulus but only every other point will give a convex vertex point, the others while still in the annulus will give the next "smaller" vertex sequence.

Now imagine that we increase the unit circle radius to 2 but keep the same point density p overall. The area of the circle quadruples, so now have ~$4N$ points in the new circle. We have also added some total number of new vertex sequences $m_\delta$. Now we have a total number of vertex sequences $m_2=m_1+m_\delta=m_1+\sqrt{8}N$

So now we have a total of $m_2$ vertex sequences in the 2 unit circle for 4N total points. If we increase to radius 3 we get: $m_3=m_1+2m_\delta=m_1+2\sqrt{8}N$...and so on: $$m_k=m_1+k\sqrt8N$$

While the total number of points is at the kth radius is $$N_k=Nk^2$$ So we see that $$m_k(N_k)=m_1+\sqrt\frac{8N_k}{N}N=m_1+\sqrt{8p\pi*N_k}$$

$m_1$ becomes a constant which depends on p the original point density. So for large N it goes as the square root function.

For a square the same argument could be applied, but with large N it should converge to the same answer as you move towards the center of the square. I think with the square you get that the convex vertex sequences converge to a unit shape: $$x^t+y^t=1^t$$ which int the $\lim_{t\to\infty}$ becomes a square.