New Constructions of SSPDs and their Applications

2025/12/09 by Abam, Mohammad A., Har-Peled, Sariel
Computer Science · Engineering · #Computational Geometry and Mesh Generation #graph theory and CDMA systems #Complexity and Algorithms in Graphs

paper · doi:10.48550/arxiv.2512.08619

Abstract

\renewcommand\Reℝ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² n) that has a separator of size O\pthn^1-1/d.

Citations

• A Practical Approach for Computing the Diameter of a Point Set

Related

• Well-Separated Pairs Decomposition Revisited
• The well-separated pair decomposition for balls
• Few Cuts Meet Many Point Sets
• Preprocessing power weighted shortest path data using a s-Well Separated Pair Decomposition
• Towards an O(√[3]log n)-Approximation Algorithm for \sc Balanced Separator