Expected distance between two random points and the shortest path problem

It has been reported that the expected Euclidean distance from a random point within a square of side length a to another random point located within an equivalent adjacent square is 1.2(a). This distance has been used to help determine an upper bound for the expected length of the shortest path through n uniformly dispersed points over a large area. Herein, it is shown that this distance of 1.2(a) is wrong, and, hence, the value for the upper bound is inaccurate. In this paper, the expected Euclidean distance between two random points in adjacent squares is determined, analytically, to be approximately 1.088(a). This number is then used, via the band heuristic methodology, to determine new estimates for the expected length of the shortest path through n points over a large region. Some avenues of future research are also included.

Expected distance between two random points and the shortest path problem Conference Paper