平面内で最も近い複数のペアの決定

Question

以下に概略を示す掃引アルゴリズムを使用して平面内の最も近い頂点のペアを決定する場合、追加の実行を行わずに複数のペアを決定できますか？

1. x座標に応じてポイントをソートします。
2. ポイントのセットを垂直線x = xmidで2つの等しいサイズのサブセットに分割します。 問題を再帰的に左右のサブセットで解決します。これにより、それぞれ左側および右側の最小距離dLminおよびdRminが得られる。
3. 1組のポイントが分割垂直の左側にあり、もう1つのポイントが右側にあるポイントのペアの最小距離dLRminを求めます。
4. 最終的な答えは、dLmin、dRmin、およびdLRminの最小値です。

Answer 1

は、あなたが半分のポイントのペアの最小距離を発見された場合、あなたが最小距離とペアを記録することができますように私には思えます。同じ距離の他のペアが見つかった場合は、そのペアを何らかのコレクションにプッシュすることで、すべてのペアを覚えています。これを左と右の半分で行い、スライバの場合は中央でチェックし、最小距離に対応するリストのすべての記録された要素を印刷することができるはずです。ような何か：

AllPairsMinDist(points[1...n]) 
    sort points according to x coordinate 
    return AllPairsMinDistInternal(points[1...n]) 

AllPairsMinDistInternal(points[1...n]) 
    if n = 1 then 
     return (+infinity, []) 
    else if n = 2 then 
     d = distance(points[1], points[2]) 
     c = (points[1], points[2]) 
     return (d, c) 
    else then 
     (dL, cL) = AllPairsMinDistInternal(points[1...floor(n/2)]) 
     (dR, cR) = AllPairsMinDistInternal(points[floor(n/2)+1...n]) 
     (dM, cM) = PairsMinDistMiddle(points[1...n], dL, dR) 
     dMin = min(dL, dR, dM) 
     cMin = [] 
     if dL = dMin then cMin = cMin union cL 
     if dR = dMin then cMin = cMin union cR 
     if dM = dMin then cMin = cMin union cM 
     return (dMin, cMin) 

AllPairsMinDistMiddle(points[1...n], dL, dR) 
    if n = 1 then 
     return (+infinity, []) 
    else if n = 2 then 
     d = distance(points[1], points[2]) 
     c = (points[1], points[2]) 
     return (d, c) 
    else then 
     xV = (points[floor(n/2)].x + points[floor(n/2)+1].x)/2 

     minD = min(dL, dR) 
     minC = [] 

     ll = binary search for index of point with smallest 
      x coordinate satisfying xV - x <= minD 

     rr = binary search for index of point with largest 
      x coordinate satisfying x - xV <= minD 

     for i = ll to floor(n/2) do 
      for j = floor(n/2) + 1 to rr do 
       d = distance(points[i], points[j]) 
       if d = minD then 
        minC = minC union [(points[i], points[j])] 
       else if d < minD then 
        minD = d 
        minC = [(points[i], points[j])] 

     alternative to for loop: 
      (dMin, cMin) = AllPairsMinDistInternal(points[ll...rr]) 

     return (dMin, cMin) 

は、上記のいくつかの問題は、おそらくあります - 私はちょうど一種のアドホック本当に使われているアルゴリズムを理解せずにそれを入力した - しかし、あなたのハイレベルの記述から、これはなんとか聞こえます。

Answer 2

等価最短ペアを別のリストに格納する必要があります。

2つの距離を比較するときは、必ず最短のものと別のリストのものを比較する必要があります。

短い場合は、リストを空にします。

等しい場合は、リストに追加します（おそらく両方のペア）。

定数時間ストアを使用すると、アルゴリズムの複雑さが低下することはありません。