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

Given a geometric graph G=(S,E)G=(S,E) in RdRd with constant dilation t, and a positive constant ε  , we show how to construct a (1+ε)(1+ε)-spanner of G   with O(|S|)O(|S|) edges using O(sort(|E|))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⊂RdS⊂Rd using O(sort(|S|))O(sort(|S|)) memory transfers.