Проблема ближайшей пары точек - Closest pair of points problem

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

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

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

Алгоритм грубой силы

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

minDist = бесконечностьза я = 1 к длина(п) - 1 делать    за j = я + 1 к длина(п) делать        позволять п = п[я], q = п[j]        если расстояние(п, q) < minDist  тогда            minDist = расстояние(п, q)            ближайшая пара = (п, q)возвращаться ближайшая пара

Планарный корпус

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

  1. Отсортируйте точки по их x-координатам.
  2. Разделите набор точек на два подмножества равного размера вертикальной линией Икс=Икссередина.
  3. Решите задачу рекурсивно в левом и правом подмножествах. Это дает минимальные расстояния слева и справа. dLmin и dRmin, соответственно.
  4. Найдите минимальное расстояние dLRmin среди множества пар точек, в которых одна точка лежит слева от разделяющей вертикали, а другая - справа.
  5. Окончательный ответ - минимум среди dLmin, dRmin, и dLRmin.
Разделяй и властвуй: наблюдение из разреженных ящиков

Оказывается, шаг 4 можно выполнить за линейное время. Опять же, наивный подход потребовал бы вычисления расстояний для всех пар левых и правых, то есть в квадратичном времени. Ключевое наблюдение основано на следующем свойстве разреженности набора точек. Мы уже знаем, что ближайшая пара точек не дальше, чем dist = min (dLmin, dRmin). Следовательно, для каждой точки п слева от разделительной линии мы должны сравнить расстояния до точек, лежащих в прямоугольнике размеров (расст, 2 ⋅ расст) граничащей с разделительной линией с правой стороны, как показано на рисунке. Причем этот прямоугольник может содержать не более шести точек с попарными расстояниями не менее dRmin. Следовательно, достаточно вычислить не более 6п расстояние влево-вправо на шаге 4.[6] Рекуррентное соотношение для числа шагов можно записать как Т(п) = 2 Т(п/2) + О(п), которую мы можем решить с помощью основная теорема для повторений "разделяй и властвуй" получить О(п бревно п).

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

Динамическая задача ближайшей пары

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

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

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

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

Смотрите также

Примечания

  1. ^ а б М. И. Шамос и Д. Хоуи. «Ближайшие проблемы». В Proc. 16-й ежегодный IEEE Симпозиум по основам информатики (FOCS), стр. 151–162, 1975 (DOI 10.1109 / SFCS.1975.8 )
  2. ^ К. Л. Кларксон, "Быстрые алгоритмы для задачи всех ближайших соседей", FOCS 1983.
  3. ^ С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979
  4. ^ С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для задачи ближайшей пары. Инф. Вычисл., 118 (1): 34–37, 1995.
  5. ^ Ричард Липтон (24 сентября 2011 г.). «Рабин подбрасывает монету».
  6. ^ Кормен, Лейзерсон, Ривест и Штейн, 2001.
  7. ^ Сури, Субхаш. «Проблема ближайшей пары» (PDF). Калифорнийский университет в Санта-Барбаре.
  8. ^ Мордехай Голин, Раджив Раман, Кристиан Шварц, Мишель Смид, «Рандомизированные структуры данных для динамической задачи о ближайших парах», SIAM J. Comput., vo. 27, нет. 4 января 1998 г., предварительная версия сообщена на 4-м Annu. ACM-SIAM Symp. по дискретным алгоритмам, стр. 301–310 (1993)
  9. ^ Сергей Беспамятных, Оптимальный алгоритм поддержания ближайшей пары. Дискретное вычисление. Геом., 19: 175-195, 1998.

Рекомендации