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

abstract

  • 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.

published proceedings

  • Industrial Engineering Research - Conference Proceedings

author list (cited authors)

  • Hale, T. S., & Smith, D. R

complete list of authors

  • Hale, TS||Smith, DR

publication date

  • December 1997