Shortest path through $n^{1/3}$ points out of $n$

Question

Say I sample $n$ points uniformly at random in the unit cube in $\mathbb{R}^3$, and then I look for the shortest path through $n^{1/3}$ of those points (rounding up, say). What happens to the length of this path as $n\to\infty$? Does it increase, decrease, or converge (or "none of the above")?

This question is the three-dimensional version of the following earlier question:

Shortest path through $\sqrt{n}$ points out of $n$

I have tried to apply the lower bounds proposed in that question, but it does not seem to me that they scale in the necessary way when we go from two to three dimensions.

Answer 1

There's an easy upper bound of $3$, indepdendent of the distribution:

Let $m = \lfloor n^{1/3}\rfloor$. Divide the cube into $m^2$ rods, each of which has size $1/m \times 1/m \times 1$ in $xyz$-coordinates.

By the pigeonhole principle, at least one rod has $n/m^2$ points in it, and therefore at least $n^{1/3}$ points. In that rod, link the first $n^{1/3}$ points from top to bottom with segments parallel to the axes.

That path includes at most $n^{1/3}-1$ segments parallel to the $x$-axis of length at most $1/m$, at most $n^{1/3}-1$ segments parallel to the $y$-axis of length at most $1/m$, and segments parallel to the $z$-axis of length at most 1. So the total length is at most $1+2(n^{1/3}-1)/m$, which is at most 3.

Answer 2

The lower bound argument I gave for $\sqrt{n}$ points in a square works here, too. I have tried to simplify it. The idea is to use the union bound: The probability that a random path with $m=\lfloor \sqrt[3]{n} \rfloor$ steps has length less than some constant is small. It is so small that the expected number of ways to choose a short path is less than $1$, so the probability is less than $1$, in fact with probability going to $1$ there is no such short path using $m$ vertices out of $n$.

It helps to suppose the points are chosen from a fine lattice $\{1/\ell,2/\ell,...\}^3$ with $\ell \gg m$, and to estimate the probability that the sum of the $L^1$ distances along the path is small rather than the $L^2$ distance. Pushing the points to be on a fine lattice does not change the length much, less than $2\sqrt{3}m/\ell$.

The count of sequences of $m$ nonnegative steps of total $L^1$ length up to $d$ is the number of ways of distributing $d$ objects among $3m+1$ categories, $d+3m \choose 3m$. There are at most $2^{3m}$ choices of signs. So, the probability that a random path with $m$ steps has $L^1$ length at most $c \ell$ is at most $2^{3m}{c \ell +3m \choose 3m} /\ell^{3m} \le \frac{2^{3m}(c \ell + 3m)^{3m}}{(3m)!\ell^{3m}} = \frac{(2c+6m/\ell)^{3m}}{(3m)!}$. If $c \ell \gt 3m$ we can estimate this as less than $\frac{(4c)^{3m}}{(3m)!}$. (Actually, we don't need to accept this factor of $2$.) Using $x! \gt (x/3)^x$, this is less than $\left(\frac{4c}{m}\right)^{3m}$.

The number of ways to choose an $m$ step path from $n$ points is at most $n\times(n-1)\times(n-2)...\times(n-m) \le n^{m+1} \approx m^{3m+3}.$

The expected number of paths with $m$ steps of $L^1$ length less than $c$ is at most $m^{3m+3}\left(\frac{4c}{m} \right)^{3m} =m^3 (4c)^{3m}$. So, if we choose $c \lt 1/4$ then as $m,n \to \infty$, the probability that there is a path with $L^1$ length smaller than $c$ goes to $0$.

The Euclidean length is up to $\sqrt{3}$ times smaller than the $L^1$ length, so the probability that there is a path through $\sqrt[3]{n}$ points with Euclidean length less than $1/(4\sqrt{3})$ goes to $0$ as $n \to \infty$.

The constant can be improved easily by a factor of $2$, and with a little work one can estimate the probability that the $L^2$ distance is small directly instead of the $L^1$ distance, and this should improve the constant significantly, too. The convenient estimate $x! \gt (x/3)^x$ can be improved to a lower bound of roughly $(x/e)^x$ from Stirling's formula which improves the constant a bit more.