十分に分離されたペア分解

計算幾何学において、点の集合の十分に分離されたペア分解 (WSPD)とは、各ペアが十分に分離された集合のペアのシーケンスであり、2 つの異なる点ごとに、その 2 つを分離するペアが 1 つだけ存在します。 ${\displaystyle S\subset \mathbb {R} ^{d}}$${\displaystyle (A_{i},B_{i})}$${\displaystyle p,q\in S}$

十分に分離されたペア分解によって誘導されるグラフは、完全ユークリッドグラフのk-スパナーとして機能し、これに関連するいくつかの問題の解を近似するのに役立ちます。^[1]

を 内の 2 つの互いに素な点の集合とし、を内の点の軸に沿った最小境界ボックスとし、 を分離係​​数とします。 ${\displaystyle A,B}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle R(X)}$${\displaystyle X}$${\displaystyle s>0}$

と のそれぞれに対して、それを含む半径 のd球が存在し、2つの球の最小距離が少なくとも であるとき、とは十分に離れているとみなします。^[2]${\displaystyle A}$${\displaystyle B}$${\displaystyle R(A)}$${\displaystyle R(B)}$${\displaystyle \rho}$${\displaystyle s\rho }$

の十分に分離された部分集合のペアの列を、任意の2つの異なる点に対して、正確に1つの、が存在し、以下のいずれかを満たす 場合、の十分に分離されたペア分解（WSPD）であるとみなします。${\displaystyle S}$${\displaystyle (A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})}$${\displaystyle S}$${\displaystyle p,q\in S}$${\displaystyle i}$${\displaystyle 1\leq i\leq m}$

• ${\displaystyle p\in A_{i}}$および、または${\displaystyle q\in B_{i}}$
• ${\displaystyle q\in A_{i}}$そして[ ^1]${\displaystyle p\in B_{i}}$

公平な分割木を構築することによって、時間的にサイズのWSPDを構築することが可能です。^[2]${\displaystyle O(s^{d}n)}$${\displaystyle O(n\lg n)}$

点集合Sの分割ツリーの一般原則は、ツリーの各ノードu が点集合S _{u を}表し、 S _uの境界ボックスR(S _u )が最長辺に沿って 2 つの等しい部分に分割され、 uの 2 つの子とそれらの点集合が形成されるというものです。これは、集合内の点が 1 つだけになるまで再帰的に実行されます。

L _max (R(X))は点集合Xの境界超矩形の最長区間のサイズを表し、L _i (R(X))は点集合Xの境界超矩形のi番目の次元のサイズを表します。以下に Split tree 計算の疑似コードを示します。

SplitTree(S) |S| = 1の場合、u をS
    のノードと
    します。R (u) := R(S) // R(S)は、各辺の長さが 0 の超長方形です。 
        S の唯一の点
    をu
        に格納します。そうでない場合はR(S)
        を計算します。 i番目の次元を、 L max (R(S)) = L i (R(S)) となる次元とします
        。R ( S )をi番目の次元に沿って2 つの同じサイズの超長方形に
        分割し、これらの超長方形に含まれる点を取り、 2 つの集合S vとS wを形成します。
         v := SplitTree(S v ) 
        w := SplitTree(S w ) vとw をそれぞれuの左と右の子として
        格納します。
         R(u) := R(S) 
    u を返します。 

このアルゴリズムは時間内に実行されます。 ${\displaystyle O(n^{2})}$

以下に、時間内に実行されるより効率的なアルゴリズムを示します。目標は、再帰のステップごとにリストをループし、毎回最大で半分のポイントに対してのみ再帰を呼び出すことです。 ${\displaystyle O(n\lg n)}$${\displaystyle O(n)}$

S _i ^{j を}Sのj番目の点のi番目の座標とし、S i_をi番目の座標に従ってソートし、その点をp(S _i ^j )とします。また、 h(R(S)) をR(S)の最長辺を 2 つに分割する超平面とします。アルゴリズムの擬似コードを以下に示します。

SplitTree(S, u) 
    if  |S| = 1 
        R(u) := R(S) // R(S)は各辺の長さが 0 の超長方形です。S内の唯一の点をu
        に格納します。
    そうでない場合は、size := |S|を繰り返します。R(S)
            を計算します。 R(u) := R(S) j : = 1 k : = |S| i番目
            の次元を、L max (R(S)) = L i (R(S)) S v  : = ∅ S w  : = ∅ただし、S i j+1 < h(R(S))かつS i k-1 > h(R(S)) の場合とします。 size := size - 1 S v  : = S v ∪ {p(S_i^j) }
                 S w  : = S w ∪ {p(S_i^k) }
                 j := j + 1 k := k - 1
        
        
            
            
            
            
            
               
                
                
                
            vとw をそれぞれuの左と右の子とします
            。if
             S  i j +1 > h(R(S)) 
                S w  := S \ S v
                 u := w 
                S := S w
                 SplitTree(S v ,v) 
            else if  S i k-1 < h(R(S)) 
                S v  := S \ S w
                 u := v 
                S := S v
                 SplitTree(S w ,w) 
        until  size ≤ n ⁄ 2
         SplitTree(S,u)

各ノードのソートされたリストを維持できるようにするには、リンク リストを使用します。各リストには、他のリストへのクロス ポインターが保持され、一定時間でポイントを取得できます。上記のアルゴリズムでは、ループの各反復で再帰呼び出しが行われます。実際には、ポイントを再ソートするオーバーヘッドなしでリストを再構築するには、すべてのポイントがノードに割り当てられたら、ソートされたリストを再構築する必要があります。再構築を行うには、各次元の各リストに沿って進み、各ポイントをそのノードの対応するリストに追加し、元のリストにクロス ポインターを追加して、新しいリストのクロス ポインターを追加できるようにします。最後に、各ノードとそのセットで再帰を呼び出します。

WSPD は、分割ツリー内のすべてのノードの子に対して再帰FindPairs(v,w)関数を呼び出すことによって、このような分割ツリーから抽出できます。 u _l / u _{r は}ノードuの子を表します。以下にFindWSPD(T, s)関数の疑似コードを示します。

分割木Tの葉ではない各ノードuに対してFindWSPD(T, s)を
    実行し、 
        FindPairs(u l , u r )
を実行する。 

以下にFindPairs(v, w)関数の疑似コードを示します。

FindPairs(v, w) は
    、 S vとS wがsに関して十分に離れている場合に、 pair(S v , S w )を 
        報告し、そうでない場合は( L max (R(v)) ≤ L max (R(w)) )となる。
    
        FindPairs(v, w l )とFindPairs(v, w r )
        を
            再帰的に呼び出します。そうでない場合はFindPairs(v l , w)とFindPairs(v r , w)を
            再帰的に呼び出します。

FindPairs(v,w)のすべての呼び出しから得られたs十分に分離されたペアを組み合わせると、分離sのWSPDが得られます。

再帰ツリーが 2 つに分割されるたびに、分解に 1 つのペアが追加されます。したがって、アルゴリズムの実行時間は、最終的な分解のペアの数になります。

CallahanとKosarajuは、このアルゴリズムがサイズ のWell-separated pair decomposition (WSPD)を見つけることを証明した。^[2]${\displaystyle O(s^{d}n)}$

補題 1 :を に関して十分に離れたペアとします。 およびとします。このとき、 です。 ${\displaystyle \{A,B\}}$${\displaystyle s}$${\displaystyle p,p'\in A}$${\displaystyle q\in B}$${\displaystyle |pp'|\leq (2/s)|pq|}$

証明:と は同じ集合にあるため、 となります。ここで は、および を囲む円の半径です。と は2 つの十分に離れた集合にあるため、 となります。次の式が得られます。 ${\displaystyle p}$${\displaystyle p'}$${\displaystyle |pp'|\leq 2\rho }$${\displaystyle \rho}$${\displaystyle A}$${\displaystyle B}$${\displaystyle p}$${\displaystyle q}$${\displaystyle |pq|\geq s\rho }$

${\displaystyle {\begin{aligned}&{\frac {|pp'|}{2}}\leq \rho \leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&{\frac {|pp'|}{2}}\leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&|pp'|\leq {\frac {2}{s}}|pq|\\\end{aligned}}}$

補題 2 :を に関して十分に離れたペアとします。 およびとします。このとき、 です。 ${\displaystyle \{A,B\}}$${\displaystyle s}$${\displaystyle p,p'\in A}$${\displaystyle q,q'\in B}$${\displaystyle |p'q'|\leq (1+4/s)|pq|}$

証明: 三角不等式により次のようになります。

${\displaystyle |p'q'|\leq |p'p|+|pq|+|qq'|}$

補題1から次の式が得られます。

${\displaystyle {\begin{aligned}|p'q'|&\leq (2/s)|pq|+|pq|+(2/s)|pq|\\&=(1+4/s)|pq|\end{aligned}}}$

適切に分離されたペア分解は、さまざまな問題を解決するために応用できます。WSPD は次の目的で使用できます。

• 時間内に最も近いペア問題を解く。^[1]${\displaystyle O(n\lg n)}$
• k-最も近いペア問題を時間内に解く。^[1]${\displaystyle O(n\lg n+k)}$
• k-最も近いペア問題を時間内に解く。^[3]${\displaystyle O(n\lg n)}$
• 全近傍問題を時間内に解く。^[1]${\displaystyle O(n\lg n)}$
• 時間内に設定された点の直径の近似値を提供します。^[1]${\displaystyle (1-\epsilon )}$${\displaystyle O(n\lg n)}$
• 点集合のtスパナーを直接誘導する。 ^[1]
• 時間的にd次元のユークリッド最小全域木のt近似を与える。^[1]${\displaystyle O(n\lg n)}$
• 時間的にd次元のユークリッド最小全域木の近似値を与える。^[4]${\displaystyle (1+\epsilon )}$${\displaystyle O(n\lg n+(\epsilon ^{-2}\lg ^{2}{\frac {1}{\epsilon }})n)}$