Sparse geometric graphs with small dilation

Given a set S of n points in R D, 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(n log n). 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. 1 Preliminaries and introduction A geometric network is an undirected graph whose vertices are points in R D. Geometric networks, especially geometric networks of points in the plane, arise in many applications. Road networks, railway networks, computer networks—any collection of objects that have some connections between them can be modeled as a geometric network. A natural and widely studied type of geometric network is the Euclidean network, where the weight of an edge is simply the Euclidean distance between its two endpoints. Such networks for points in R D form the topic of study of our paper. When designing a network for a given set S of points, several criteria have to be taken into account. In particular, in many applications it is important to ensure a short connection between every two points in S