algorithm - 直線上に与えられた点を持つ最短距離のペア?

Question

誰かがソートされていない共線点の最短距離のペアを見つけるアルゴリズムを提案できますか?

2Dで最も近い点のペアを実行し、線に適用するだけで、O(nlogn)でこれを行う1つのソリューションがあります。しかし、これをより効率的に行うことはできますか?

Answer 1

ポイントをソートする必要があるのではないかと心配していますが、これには少なくとも O(n*log(n)) 時間かかります (バケット ソートを使用できない場合)。

Answer 2

回転変換を実行することで、2D ケースを 1D ケースにいつでも縮小できることに注意してください。

残念ながら、一般的なケースでは O(nlogn) よりもうまくいくとは思いません。あなたの最善の選択肢は、それらを並べ替えてからリストをトラバースすることです。

Answer 3

これは、平面内の最も近い点のペアに対して予想される O(n) 時間のアルゴリズムです。
これは、Kleinberg と Tardos による Algorithm Design の本からのものです。

これはPythonのような疑似コードです

def Bucket(point, buck_size):
  return int(point[0] / buck_size, int(point[1] / buck_size)

def InsertPoint(grid, point, buck_size):
  bucket = Bucket(point, buck_size)
  grid[buck_size].append(point)

def Rehash(points, limit, buck_size):
  grid = collections.defaultdict(list)
  for first limit point in points:
    InsertPoint(grid, point, buck_size)
  return grid

# return new distance if point is closer than buck_size to any point in grid,
# otherwise return inf
def Probe(grid, point, buck_size):
  orig_bucket = Bucket(point)
  for delta_x in [-1, 0, 1]:
    for delta_y in [-1, 0, 1]:
      next_bucket = (orig_bucket[0] + delta_x, orig_bucket[1] + delta_y)
      for cand_point in grid[next_bucket]:  
        # there at most 2 points in any cell, otherwise we rehash 
        # and make smaller cells.
        if distance(cand_point, point) < buck_size):
          return distance(cand_point, point)
  return inf

def ClosestPair(points):
   random_shuffle(points)
   min_dist = distance(points[0], points[1])
   grid = Rehash(points, 2, min_dist)
   for i = 3 to n
     new_dist = Probe(points, i, grid)
     if new_dist != inf:
        # The key to the algorithm is this happens rarely when i is close to n,
        # and it's cheap when i is close to 0.
        grid = Rehash(points, i, new_dist)
        min_dist = new_dist
     else:
        InsertPoint(point, grid, new_dist)
   return min_dist

各近隣候補検索は O(1) であり、いくつかのハッシュで行われます。アルゴリズムは O(log(n)) 回の再ハッシュを行うと予想されますが、それぞれに i に比例する時間がかかります。再ハッシュが必要になる確率は 2/i (== この特定の点がこれまでで最も近いペアである可能性は?) であり、i 個の点を調べた後にこの点が最も近いペアである確率です。したがって、期待されるコストは

sum_i=2^n Prob[ステップ i での再ハッシュ] * コスト (i での再ハッシュ) + O(1) =

sum_i=2^n 2/i * i + O(1) =

sum_i=2^n 2 + O(1) =

の上）

Answer 4

限られた範囲の番号のリストがある場合の解決策を提案します。

すべての数値が[a、b]の範囲内にあり、O（ba）<O（nlog（n））の場合、O（max（ba、n））で実行できます。

サイズbaの配列を作成します。すべてを0に開始できます（O（1）でこれを行うためのアルゴリズムがあります）

リストに目を通し、値xごとに、セルのxaの場所に「1」を入力します。

次に、新しい配列に目を通し、値を持つセル間の距離を数えます。

このようにして、最小距離を見つけ、新しい配列にあるインデックスによって実際の値を取得できます。