New constructions of SSPDs and their applications
Mohammad Ali Abam, Sariel Har-Peled · 2010
We present a new optimal construction of semi-separated pair decomposition (SSPD) for a set of n points in IRd. 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 > 1, we present a new construction of a t-spanner with O(n) edges and maximum degree O(log2 n) that has a separator of size O(n1-1/d).