Given a set S of n points in RD, and an integer k such that 0≤k<n, we show that a geometric graph with vertex set S, at most n-1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n-1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.

Additional Metadata
Keywords Dilation, Geometric network, Small-dilation spanning tree, Spanner
Persistent URL dx.doi.org/10.1016/j.comgeo.2007.07.004
Journal Computational Geometry
Citation
Aronov, B. (Boris), De Berg, M. (Mark), Cheong, O. (Otfried), Gudmundsson, J. (Joachim), Haverkort, H. (Herman), Smid, M, & Vigneron, A. (Antoine). (2008). Sparse geometric graphs with small dilation. Computational Geometry, 40(3), 207–219. doi:10.1016/j.comgeo.2007.07.004