2025/09/07 by Har-Peled, Sariel, Raichel, Benjamin, Robson, Eliot W.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.05997
We revisit the notion of WSPD (i.e., well-separated pairs-decomposition), presenting a new construction of WSPD for any finite metric space, and show that it is asymptotically instance-optimal in size. Next, we describe a new WSPD construction for the weighted unit-distance metric in the plane, and show a bound O( ε-2 n log n) on its size, improving by a factor of 1/ε2 over previous work. The new construction is arguably simpler and more elegant. We point out that using WSPD, one can approximate, in near-linear time, the distortion of a bijection between two point sets in low dimensions. As a new application of WSPD, we show how to shortcut a polygonal curve such that its dilation is below a prespecified quantity. In particular, we show a near-linear time algorithm for computing a simple subcurve for a given polygonal curve in the plane so that the new subcurve has no self-intersection.