Наименьшее расстояние пары с точками на линии?

Question

Может кто-нибудь предложить алгоритм, чтобы найти пару кратчайших расстояний несортированных, коллинеарных точек?

У меня есть одно решение, которое делает это в O(nlogn), просто делая ближайшую пару точек в 2D и применяя к линии. Однако можно ли сделать это более эффективно?

Answer 1

Обратите внимание, что вы всегда можете уменьшить 2D-случай до 1D, выполнив преобразование вращения.

К сожалению, я не думаю, что вы можете сделать лучше, чем O(nlogn) в общем случае. Лучшим вариантом будет отсортировать их, а затем просмотреть список.

Answer 2

Боюсь, вам нужно отсортировать точки, что займет у вас не менее O(n*log(n)) времени (если вы не можете использовать сортировку по сегментам), поэтому я сомневаюсь, что вы найдете более быстрый алгоритм для этого.

Answer 3

Это ожидаемый O (n) алгоритм времени для ближайшей пары точек на плоскости.
Это из книги "Разработка алгоритмов" Кляйнберга и Тардоса.

Вот это в 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)

Создайте массив размером ba. Вы можете установить все это в 0 (есть алгоритм для этого в O(1))

просмотрите список и для каждого значения x поместите "1" в ячейку вместо xa.

Затем перейдите к новому массиву и посчитайте расстояния между ячейками, которые имеют значение.

Таким образом, вы можете найти минимальное расстояние и получить фактические значения по индексу, который они имеют в новом массиве.