Assume space is uniformly filled with random points placed by a spatial Poisson process of a given intensity $\rho$. I try to move from the origin to some remote point (which we can take to be directly along the x-axis), but can only move between points closer than unit distance. The resulting optimal trajectory will have a total length $D$ larger than the actual distance $d$ to the target point. What is the distribution or expectation of $D/d$?
Clearly, if $\rho$ is too small we are below the continuum percolation threshold and I will not get anywhere. So let us assume $\rho$ is large enough.
If I look at the first step, the distance I will manage along the x-axis will be the largest x-coordinate of the points in the unit sphere. It is not that hard to calculate the maximum order statistic for a given number of points $n\sim (4\pi/3)\rho$: the distribution is $f(x)=(3/4)(1-x^2)$, the cdf is $F(x)=(3x-x^3+2)/4$, the distribution of the maximum is $f_{(n)}(x)=(3n/4^n)(3x-x^3+2)^{n-1}(1-x^2)$. The expectation is a messy polynomial but asymptotes towards 1, with $E[f_{(5)}]>1/2$ and $E[f_{(109)}]>0.9$.
However, (1) the number of points is actually a random variable, and (2) on the next step I also have a lateral deviation dependent on the y- and z-coordinates of the point that needs to be removed eventually.
Empirically, the distribution of $D/d$ looks like it approaches a Gaussian as I increase $d$, although it looks like the kurtosis is a bit high.
Any thoughts of how to characterise the distribution as a function of $d$ and $\rho$? Or just a better way of estimating the expectation than running lots of Monte Carlo simulations?
