New Constructions of SSPDs and their Applications

Abstract

We present a new optimal construction of a semi-separated pair decomposition (i.e., SSPD) for a set of $n$ points in ${\Re }^d$. 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({\log }^{2}n)$ that has a separator of size $O\pth{n^{1-1/d}}$.

Appeard in SoCG 2010 and CGTA

References in corpus (1)

• Fast Construction of Nets in Low Dimensional Metrics, and Their Applications

Cited by in corpus (2)

• Local Doubling Dimension of Point Sets
• On Clusters that are Separated but Large