Home Bookmarks Papers Blog

New Constructions of SSPDs and their Applications

M. A. Abam and Sariel Har-Peled.


We present a new optimal construction of semi-separated pair decomposition (SSPD) for a set of n points in Rd. 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, we present a new construction of a \tspanner with O(n) edges and maximum degree O( log2 n) that has a separator of size O(n1-1/d).


Postscript, PDF.
Talk slides and source.
Last modified: Sun Jun 20 11:28:16 CDT 2010