@inproceedings{26f16c578e82492f823fc3b7e9017843,

title = "New constructions of SSPDs and their applications",

abstract = "We present a new optimal construction of semi-separated pair decomposition (SSPD) for a set of n points in ℝ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(log2 n) that has a separator of size O (n1-1/d).",

keywords = "Geometric spanners, Separated pair decomposition, Separators",

author = "Abam, {Mohammad Ali} and Sariel Har-Peled",

year = "2010",

month = jul,

day = "30",

doi = "10.1145/1810959.1810993",

language = "English (US)",

isbn = "9781450300162",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "192--200",

booktitle = "Proceedings of the 26th Annual Symposium on Computational Geometry, SCG'10",

note = "26th Annual Symposium on Computational Geometry, SoCG 2010 ; Conference date: 13-06-2010 Through 16-06-2010",

}