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

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

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

Наивный алгоритм поиска расстояний между всеми парами точек в пространстве размерности d и выбора минимума требует времени O ( n ² ) . Оказывается, проблема может быть решена за O ( n log n ) времени в евклидовом пространстве или L ^p пространстве фиксированной размерности d. ^[2] В алгебраического дерева решений модели вычислений , в O ( п войти п ) алгоритм является оптимальным, за счет уменьшения от проблемы единственности элемента. В вычислительной модели, которая предполагает, что нижняя функция вычислима за постоянное время, проблема может быть решена за время O ( n log log n ) . ^[3] Если мы позволим использовать рандомизацию вместе с функцией минимума, проблема может быть решена за время O ( n ) . ^{[4] [5]}

Алгоритм грубой силы [ править ]

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

minDist = бесконечность для  i = 1 до длины ( P ) - 1 do  для  j = i + 1 до длины ( P ) действительно  let  p = P [ i ], q = P [ j ], если  dist ( p , q ) < minDist  тогда  minDist = dist ( p , q ) closestPair = (p , q ) вернуть  ближайшую пару

Планарный случай [ править ]

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

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 . Следовательно, достаточно вычислить не более 6 n расстояний влево-вправо на шаге 4. ^[6] Рекуррентное соотношение для количества шагов можно записать как T ( n ) = 2 T ( n / 2) + O ( n ) , которую мы можем решить, используя основную теорему для повторений «разделяй и властвуй», чтобы получить O ( n log n ) .

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

Задача динамической ближайшей пары [ править ]

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

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

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]