Approximating the average stretch factor of geometric graphs

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