Approximating the average stretch factor of geometric graphs

Let G be a geometric graph whose vertex set S is a set of n points in ℝ d . The stretch factor of two distinct points p and q in S is the ratio of their shortest-path distance in G and their Euclidean distance. We consider the problem of approximating the average of the n choose 2 stretch factors determined by all pairs of points in S . We show that for paths, cycles, and trees, this average can be approximated, within a factor of 1+e, in O ( n polylog( n )) time. For plane graphs in ℝ 2 , we present a (2+e)-approximation algorithm with running time O ( n 5/3 polylog( n )), and a (4+e)-approximation algorithm with running time O ( n 3/2 polylog( n )). Finally, we show that, for any tree in ℝ 2 , the exact average of the squares of the n choose 2 stretch factors can be computed in O ( n 11/6 ) time.