New constructions of SSPDs and their applications

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of n   points in RdRd. In the new construction each point participates in a few pairs, and it extends easily to spaces with low doubling dimension. This is the first optimal construction with these properties.As an application of the new construction, for a fixed t>1t>1, we present a new construction of a t  -spanner with O(n)O(n) edges and maximum degree O(log2n) that has a separator of size O(n1−1/d)O(n1−1/d).