New Constructions of SSPDs and their Applications

Mohammad A. Abam, Sariel Har-Peled

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 constructio…