Well-separated pair decomposition とは

計算幾何学において、点集合 S R d {\displaystyle S\subset \mathbb {R} ^{d}} の十分に分離された対分解(WSPD)は、各対が良好に分離されるように、対の組 ( A i , B i ) {\displaystyle (A_{i},B_{i})} の系列であり、2つの異なる点[3 ]、正確には2つを分離する1つの対が存在する。
十分に分離されたペア分解によって誘導されたグラフは、完全なユークリッドグラフのk-スパンとして機能することができ、これに関連するいくつかの問題を近似する際に有用である。