Sparse geometric graphs with small dilation

Abstract

Given a set S of n points in the plane, 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, and dilation O(n/(k+1)) can be computed in time O(n log n). We also construct n-point sets for which any geometric graph with n-1+k edges has dilation Omega(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.