Average Stretch Factor: How Low Does It Go?

作者：Dujmovic Vida^*; Morin Pat; Smid Michiel

来源：Discrete & Computational Geometry, 2015, 53(2): 296-326.

DOI：10.1007/s00454-015-9663-4

• Spanners
• Average stretch
• Average dilation

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.

• 出版日期2015-3