Задача о ближайшей паре точек

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

Сроки [ править ]

рандомизированные алгоритмы, решающие задачу за линейное время Известны , в евклидовых пространствах , размерность которых рассматривается как константа для целей асимптотического анализа . ^[2]^[3]^[4] Это значительно быстрее, чем $O(n^{2})$ время (выраженное здесь в обозначении большого О ), которое можно было бы получить с помощью наивного алгоритма поиска расстояний между всеми парами точек и выбора наименьшего.

Также возможно решение задачи без рандомизации, в с произвольным доступом машинных моделях вычислений и неограниченной памятью, позволяющих использовать функцию пола , в почти линейных $O(n\log \log n)$ время. ^[5] В еще более ограниченных моделях вычислений, таких как алгебраическое дерево решений , проблема может быть решена несколько медленнее. $O(n\log n)$ привязанный ко времени, ^[6] и это оптимально для данной модели за счет сокращения от проблемы уникальности элемента . Как алгоритмы развертки линии , так и алгоритмы «разделяй и властвуй» с этой более медленной временной границей обычно преподаются в качестве примеров этих методов разработки алгоритмов. ^[7]^[8]

с линейным Рандомизированные временем алгоритмы

Линейный рандомизированный по ожидаемому времени алгоритм Рабина (1976) , слегка модифицированный Ричардом Липтоном для упрощения анализа, работает на входном множестве следующим образом: $S$ состоящий из $n$ точки в $k$ -мерное евклидово пространство:

Выбирать $n$ пар точек равномерно случайным образом, с заменой, и пусть $d$ быть минимальным расстоянием выбранных пар.
Округлите входные точки до квадратной сетки точек, размер которой (расстояние между соседними точками сетки) равен $d$ и используйте хэш-таблицу для сбора пар входных точек, которые округляются до одной и той же точки сетки.
Для каждой входной точки вычислите расстояние до всех других входных данных, которые округляются до той же точки сетки или до другой точки сетки в Мура окрестности $3^{k}-1$ окружающие точки сетки.
Верните наименьшее из расстояний, вычисленных в ходе этого процесса.

Алгоритм всегда правильно определит ближайшую пару, поскольку он отображает любую пару, расположенную ближе, чем расстояние. $d$ к одной и той же точке сетки или к соседним точкам сетки. Равномерная выборка пар на первом этапе алгоритма (по сравнению с другим методом Рабина для выборки аналогичного количества пар) упрощает доказательство того, что ожидаемое количество расстояний, вычисленное алгоритмом, является линейным. ^[4]

Вместо этого другой алгоритм Khuller & Matias (1995) проходит две фазы: случайный итерационный процесс фильтрации, который аппроксимирует ближайшее расстояние с точностью до аппроксимации коэффициента $2{\sqrt {k}}$ , вместе с завершающим шагом, который превращает это приблизительное расстояние в точное ближайшее расстояние. Процесс фильтрации повторяет следующие шаги, пока $S$ становится пустым:

Выберите точку $p$ равномерно случайным образом от $S$ .
Вычислите расстояния от $p$ ко всем остальным точкам $S$ и пусть $d$ быть минимальным таким расстоянием.
Округлите входные точки до квадратной сетки размером $d/(2{\sqrt {k}})$ и удалить из $S$ все точки, у которых в окрестности Мура нет других точек.

Приблизительное расстояние, найденное в результате этого процесса фильтрации, является окончательным значением $d$ , вычисленный на предыдущем шаге $S$ становится пустым. На каждом шаге удаляются все точки, ближайший сосед которых находится на расстоянии. $d$ или больше, не менее половины баллов в ожидании, из чего следует, что общее ожидаемое время фильтрации линейно. Как только приблизительная стоимость $d$ известно, его можно использовать для заключительных шагов алгоритма Рабина; на этих этапах каждая точка сетки имеет постоянное количество входных данных, округленных до нее, поэтому время снова линейно. ^[3]

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

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

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

Если ограничивающая рамка для всех точек известна заранее и доступна функция пола постоянного времени, то ожидаемое значение $O(n)$ Была предложена структура данных -space, поддерживающая ожидаемое время. $O(\log n)$ вставки и удаления и постоянное время запроса. При модификации для модели алгебраического дерева решений вставки и удаления потребуют $O(\log ^{2}n)$ ожидаемое время. ^[9] Сложность упомянутого выше динамического алгоритма ближайшей пары экспоненциальна в размерности $d$ , и поэтому такой алгоритм становится менее подходящим для задач большой размерности.

Алгоритм решения динамической задачи поиска ближайшей пары в $d$ dimensional space was developed by Sergey Bespamyatnikh in 1998. ^[10] Точки можно вставлять и удалять в $O(\log n)$ время за очко (в худшем случае).

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

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

^ Шамос, Майкл Ян ; Хоуи, Дэн (1975). «Задачи ближайшей точки». 16-й ежегодный симпозиум по основам информатики, Беркли, Калифорния, США, 13-15 октября 1975 г. Компьютерное общество IEEE. стр. 151–162. дои : 10.1109/SFCS.1975.8 .
^ Рабин, М. (1976). «Вероятностные алгоритмы». Алгоритмы и сложность: последние результаты и новые направления . Академическая пресса. стр. 21–39. Цитируется Хуллером и Матиасом (1995) .
↑ Перейти обратно: Перейти обратно: ^а ^б Хуллер, Самир ; Матиас, Йоси (1995). «Простой алгоритм рандомизированного сита для решения задачи нахождения ближайшей пары» . Информация и вычисления . 118 (1): 34–37. дои : 10.1006/inco.1995.1049 . МР 1329236 . S2CID 206566076 .
↑ Перейти обратно: Перейти обратно: ^а ^б Липтон, Ричард (24 сентября 2011 г.). «Рабин подбрасывает монетку» . Потерянное письмо Гёделя и P=NP .
^ Фортуна, Стив; Хопкрофт, Джон (1979). «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации . 8 (1): 20–23. дои : 10.1016/0020-0190(79)90085-1 . hdl : 1813/7460 . МР 0515507 .
^ Кларксон, Кеннет Л. (1983). «Быстрые алгоритмы решения задачи всех ближайших соседей». 24-й ежегодный симпозиум по основам информатики, Тусон, Аризона, США, 7-9 ноября 1983 г. Компьютерное общество IEEE. стр. 226–232. дои : 10.1109/SFCS.1983.16 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «33.4: Поиск ближайшей пары точек». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 957–961. ISBN 0-262-03293-7 .
^ Кляйнберг, Джон М .; Тардос, Ева (2006). «5.4 Нахождение ближайшей пары точек». Алгоритм проектирования . Аддисон-Уэсли. стр. 225–231. ISBN 978-0-321-37291-8 .
^ Голин, Мордехай; Раман, Раджив; Шварц, Кристиан; Смид, Мишель (1998). «Рандомизированные структуры данных для динамической задачи ближайшей пары» (PDF) . SIAM Journal по вычислительной технике . 27 (4): 1036–1072. дои : 10.1137/S0097539794277718 . МР 1622005 . S2CID 1242364 .
^ Беспамятных, С.Н. (1998). «Оптимальный алгоритм обслуживания ближайшей пары» . Дискретная и вычислительная геометрия . 19 (2): 175–195. дои : 10.1007/PL00009340 . МР 1600047 .

[sh-1] Шамос, Майкл Ян ; Хоуи, Дэн (1975). «Задачи ближайшей точки». 16-й ежегодный симпозиум по основам информатики, Беркли, Калифорния, США, 13-15 октября 1975 г. Компьютерное общество IEEE. стр. 151–162. дои : 10.1109/SFCS.1975.8 .

[2] Рабин, М. (1976). «Вероятностные алгоритмы». Алгоритмы и сложность: последние результаты и новые направления . Академическая пресса. стр. 21–39. Цитируется Хуллером и Матиасом (1995) .

[km-3] Перейти обратно: Перейти обратно: ^а ^б Хуллер, Самир ; Матиас, Йоси (1995). «Простой алгоритм рандомизированного сита для решения задачи нахождения ближайшей пары» . Информация и вычисления . 118 (1): 34–37. дои : 10.1006/inco.1995.1049 . МР 1329236 . S2CID 206566076 .

[rl-4] Перейти обратно: Перейти обратно: ^а ^б Липтон, Ричард (24 сентября 2011 г.). «Рабин подбрасывает монетку» . Потерянное письмо Гёделя и P=NP .

[fh-5] Фортуна, Стив; Хопкрофт, Джон (1979). «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации . 8 (1): 20–23. дои : 10.1016/0020-0190(79)90085-1 . hdl : 1813/7460 . МР 0515507 .

[6] Кларксон, Кеннет Л. (1983). «Быстрые алгоритмы решения задачи всех ближайших соседей». 24-й ежегодный симпозиум по основам информатики, Тусон, Аризона, США, 7-9 ноября 1983 г. Компьютерное общество IEEE. стр. 226–232. дои : 10.1109/SFCS.1983.16 .

[7] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «33.4: Поиск ближайшей пары точек». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 957–961. ISBN 0-262-03293-7 .

[8] Кляйнберг, Джон М .; Тардос, Ева (2006). «5.4 Нахождение ближайшей пары точек». Алгоритм проектирования . Аддисон-Уэсли. стр. 225–231. ISBN 978-0-321-37291-8 .

[9] Голин, Мордехай; Раман, Раджив; Шварц, Кристиан; Смид, Мишель (1998). «Рандомизированные структуры данных для динамической задачи ближайшей пары» (PDF) . SIAM Journal по вычислительной технике . 27 (4): 1036–1072. дои : 10.1137/S0097539794277718 . МР 1622005 . S2CID 1242364 .

[10] Беспамятных, С.Н. (1998). «Оптимальный алгоритм обслуживания ближайшей пары» . Дискретная и вычислительная геометрия . 19 (2): 175–195. дои : 10.1007/PL00009340 . МР 1600047 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]