# Distribution of length of restricted shortest path in random point cloud

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?

• There's always a certain probability that there's no such path. If you count that as $D=\infty$, the expectation would be infinite. Alternatively, you could consider the distribution of $D$ conditional on there being a path. Jan 24, 2020 at 11:59
• Yes, conditioning on there being a path seems reasonable. Jan 24, 2020 at 12:07