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 n) on its size, improving by a factor of 1/² 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.
Har-Peled et al. (Sun,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: