Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

Given a geometric graph G=(S,E) in Rd with constant dilation t, and a positive constant , we show how to construct a (1+)-spanner of G with O(|S|) edges using O(sort(|E|)) memory transfers in the cache-oblivious model of computation. The main building block of our algorithm, and of independent interest in itself, is a new cache-oblivious algorithm for constructing a well-separated pair decomposition which builds such a data structure for a given point set S⊂Rd using O(sort(|S|)) memory transfers.