Spanners for geometric intersection graphs with applications

Abstract

A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real numbert>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of verticesu,v in G, there exists a path in G' of length at most t times the distance between u and v inG. In this paper, we consider the problem of efficiently constructing sparse spanners of ball graphs which supports fast shortest path distance queries.

We present the first algorithm for constructing spanners of ball graphs. For a ball graph in R^k, we construct a (1+ε)-spanner for any ε>0 with O(nε^-k+1) edges in O(n^2ℓ+δε^-k log^ℓ S) time, using an efficient partitioning of space into hypercubes and solving intersection problems. Here ℓ=1-1/(⌊k/2⌋+2), δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case when the balls all have unit size, we show that the complexity of constructing a (1+ε)-spanner is almost equal to the complexity of constructing a Euclidean minimum spanning tree. The algorithm extends naturally to other disk-likeobjects, also in higher dimensions.

The algorithm uses an efficient subdivision of space to construct a sparse graph having many of the same distance properties as the input ball graph. Additionally, the constructed spanners have a small vertex separator decomposition (hereditary). In dimension k=2, the disk graph spanner has an O(n^1/2ε^-3/2+ε^-3log S) separator. The presence of a small separator is then exploited to obtain very efficient data structures for approximate distance queries. The results on geometric graph separators might be of independent interest. For example, since complete Euclidean graphs are just a special case of (unit) ball graphs, our results also provide a new approach for constructing spanners with small separators in these graphs.