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

Question

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

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

Answer 1

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

Answer 2

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

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

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 Проб [Перефразировать на шаге 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.

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

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