1 Answers
In computational geometry, a well-separated pair decomposition of a set of points S ⊂ R d {\displaystyle S\subset \mathbb {R} ^{d}} , is a sequence of pairs of sets {\displaystyle } , such that each pair is well-separated, and for each two distinct points p , q ∈ S {\displaystyle p,q\in S} , there exists precisely one pair which separates the two.
The graph induced by a well-separated pair decomposition can serve as a k-spanner of the complete Euclidean graph, and is useful in approximating solutions to several problems pertaining to this.
4 views
Answered