Average Stretch Factor: How Low Does It Go?

Abstract

(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image)

In a geometric graph ......, the stretch factor between two vertices ...... and ...... is the ratio between the Euclidean length of the shortest path from ...... to ...... in ...... and the Euclidean distance between ...... and ....... The average stretch factor of ...... is the average stretch factor taken over all pairs of vertices in ....... We show that, for any constant dimension ...... and any set ...... of ...... points in ......, there exists a geometric graph with vertex set ...... that has ...... edges and that has average stretch factor ....... More precisely, the average stretch factor of this graph is ....... We complement this upper bound with a lower bound: There exist ......-point sets in ...... for which any graph with ...... edges has average stretch factor ....... Bounds of this type are not possible for the more commonly studied worst-case stretch factor. In particular, there exist point sets ...... such that any graph with worst-case stretch factor ...... has a superlinear number of edges.