RELAXED SPANNERS FOR DIRECTED DISK GRAPHS

Let (V, delta) be a finite metric space, where V is a set of n points and d is a distance function defined for these points. Assume that (V, delta) has a constant doubling dimension d and assume that each point p 2 V has a disk of radius gamma(p) around it. The disk graph that corresponds to V and gamma(.) is a directed graph I(V, E, gamma), whose vertices are the points of V and whose edge set includes a directed edge from p to q if delta(p, q) <= gamma(p). In [8] we presented an algorithm for constructing a (1+ is an element of)-spanner of size O(n/is an element of(d) logM), where M is the maximal radius gamma(p). The current paper presents two results. The first shows that the spanner of [8] is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of M. The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph I(V, E, gamma 1+ is an element of), where gamma(1)+ is an element of(p) = (1 vertical bar is an element of) . gamma(p) for every p is an element of V, then it is possible to get a (1 + is an element of)-spanner of size O(n/is an element of(d)) for I(V, E, gamma). Our algorithm is simple and can be implemented efficiently.