### Approximating the average stretch factor of geometric graphs

#### Abstract

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+ε, in*O*(*n*polylog(*n*)) time. For plane graphs in ℝ^{2}, we present a (2+ε)-approximation algorithm with running time*O*(*n*^{5/3}polylog(*n*)), and a (4+ε)-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.#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v3i1a7

ISSN: 1920-180X