Approximating the average stretch factor of geometric graphs

Siu-Wing Cheng, Christian Knauer, Stefan Langerman, Michiel Smid


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(n5/3polylog(n)), and a (4+ε)-approximation algorithm with running time O(n3/2polylog(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(n11/6) time.

Full Text:



ISSN: 1920-180X