Проблема с ближайшей парой точек

Ближайшая пара точек показана красным

Проблема с ближайшей парой точек или задача ближайшей пары - это задача вычислительной геометрии : для заданных n точек в метрическом пространстве найти пару точек с наименьшим расстоянием между ними. Ближайшая парная задача для точек на евклидовой плоскости была одной из первых геометрических задач, которые рассматривались у истоков систематического изучения вычислительной сложности геометрических алгоритмов.

Наивный алгоритм поиска расстояний между всеми парами точек в пространстве размерности d и выбора минимума требует O (n) времени. Оказывается, проблема может быть решена за O (n log n) времени в евклидовом пространстве или L пространстве фиксированной размерности d. В модели алгебраического дерева решений вычислений алгоритм O (n log n) является оптимальным путем сокращения от проблемы уникальности элемента. В вычислительной модели, которая предполагает, что функция пола вычислима за постоянное время, проблема может быть решена за время O (n log log n). Если мы позволим использовать рандомизацию вместе с функцией минимума, проблема может быть решена за время O (n).

• 1 Алгоритм грубой силы
• 2 Планарный случай
• 3 Динамический ближайший- проблема пары
• 4 См. также
• 5 Примечания
• 6 Ссылки

Ближайшая пара точек может быть вычислена в O (n) время путем выполнения перебора. Для этого можно вычислить расстояния между всеми парами точек n (n - 1) / 2, а затем выбрать пару с наименьшим расстоянием, как показано ниже.

minDist = бесконечность для i = 1 от до length (P) - 1 doдля j = i + 1 до length (P) doпусть p = P [i], q = P [j] если dist (p, q) < minDist, то minDist = dist (p, q) closestPair = (p, q) return closestPair

Проблема может быть решена за время O (n log n) с помощью рекурсивный подход разделяй и властвуй, например, следующим образом:

1. Сортирует точки в соответствии с их координатами x.
2. Разделите набор точек на два подмножества равного размера по вертикальная линия x = x mid.
3. Решите задачу рекурсивно в левом и правом подмножествах. Это дает минимальные расстояния с левой и с правой стороны d Lmin и d Rmin, соответственно.
4. Найдите минимальное расстояние d LRmin среди множества пар точек, в которых одна точка лежит слева от разделяющей вертикали, а другая - справа.
5. Окончательный ответ - минимум среди d Lmin, d Rmin и d LRmin.

Разделяй и властвуй: наблюдение в виде разреженного прямоугольника

Оказывается, шаг 4 может быть выполнен за линейное время. Опять же, наивный подход потребовал бы вычисления расстояний для всех пар левых и правых, то есть в квадратичном времени. Ключевое наблюдение основано на следующем свойстве разреженности набора точек. Мы уже знаем, что ближайшая пара точек не дальше, чем dist = min (d Lmin, d Rmin). Следовательно, для каждой точки p слева от разделительной линии мы должны сравнить расстояния до точек, которые лежат в прямоугольнике размеров (dist, 2 ⋅ dist), граничащем с разделительной линией с правой стороны, как показано на рисунке.. Более того, этот прямоугольник может содержать не более шести точек с попарными расстояниями не менее d Rmin. Следовательно, на шаге 4 достаточно вычислить не более 6n расстояний влево-вправо. Рекуррентное соотношение для количества шагов можно записать как T (n) = 2 T (n / 2) + O (n), что мы можно решить с помощью основной теоремы для повторений «разделяй и властвуй», чтобы получить O (n log n).

Поскольку ближайшая пара точек определяет ребро в триангуляции Делоне и соответствует двум соседним ячейкам на диаграмме Вороного, ближайшая пара точек может быть определяется в линейном времени, когда нам дается одна из этих двух структур. Вычисление триангуляции Делоне или диаграммы Вороного занимает время O (n log n). Эти подходы неэффективны для измерения d>2, в то время как алгоритм «разделяй и властвуй» можно обобщить так, чтобы он занимал время O (n log n) для любого постоянного значения d с экспоненциальной зависимостью от d.

динамическая версия для задачи ближайшей пары формулируется следующим образом:

• Учитывая динамический набор объектов, найдите алгоритмы и структуры данных для эффективного пересчета ближайшей пары объектов каждый раз, когда объекты вставляются или удаляются.

Если ограничивающая рамка для всех точек известна заранее, а константа - Если доступна функция пола, то была предложена ожидаемая структура данных пространства O (n), которая поддерживает вставки и удаления O (log n) в ожидаемое время и постоянное время запроса. При модификации для модели алгебраического дерева решений вставки и удаления потребуют ожидаемого времени O (log n). Однако стоит отметить, что сложность процитированного выше динамического алгоритма ближайшей пары экспоненциальна в размерности d, и поэтому такой алгоритм становится менее подходящим для задач большой размерности.

Алгоритм для динамической задачи о ближайших парах в d-мерном пространстве был разработан Сергеем Беспамятных в 1998 году. Точки можно вставлять и удалять за O (log n) раз на точку (в худшем случае).

• ГИС
• Поиск ближайшего соседа