直线上给出的点的最短距离对？

Question

有人可以建议一种算法来找出未排序的共线点的最短距离对吗？

我有一个解决方案，只需执行 二维中最接近的点对即可在 O(nlogn) 中完成此操作< /a> 并应用于该行。然而，这可以更有效地完成吗？

Answer 1

恐怕你必须对点进行排序，这至少需要 O(n*log(n)) 时间（除非你可以使用桶排序），所以我怀疑你是否找到了更快的算法。

Answer 2

请注意，您始终可以通过执行旋转变换将 2D 情况减少为 1D 情况。

不幸的是，我认为在一般情况下你不能做得比 O(nlogn) 更好。最好的选择是对它们进行排序，然后遍历列表。

Answer 3

这是平面上最接近的点对的预期 O(n) 时间算法。
它来自 Kleinberg 和 Tardos 所著的《算法设计》一书。

这是一个类似 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[Rehash at step i] * Cost(rehash at i) + O(1) =

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

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

O(n)

Answer 4

我只会针对您拥有有限范围内的数字列表的情况提出一个解决方案。

如果所有数字都在 [a,b] 范围内，其中 O(ba) < O(nlog(n)) 你可以在 O(max(ba,n)) 中完成。

创建一个大小为 ba 的数组。您可以将其全部初始化为 0（有一个算法可以在 O(1) 中完成此操作）

检查您的列表，对于每个值 x，将“1”放入单元格中 xa 的位置。

然后检查新数组，并计算具有值的单元格之间的距离。

这样您就可以找到最小距离，并通过新数组中的索引获取实际值。