#algorithm #data-structures #time-complexity #distance #point
#алгоритм #структуры данных #временная сложность #расстояние #точка
Вопрос:
Существует ли какой-либо алгоритм, лучший, чем O (n ^ 2), для соединения любых двух точек прямой линией, если их расстояние меньше постоянной t?
Я думаю о сортировке точек в соответствии с их координатой x, а затем ищу другую точку в пределах [x-t, x t]. Но худшим случаем по-прежнему является O (n ^ 2). Есть идея? Есть ли у нас какая-либо специальная структура данных для ускорения?
Комментарии:
1. Найдите «проблему с ближайшей парой».
2. Есть ли ограничение на t? В противном случае, если все точки находятся в пределах t друг от друга, то вам придется соединить каждую точку с любой другой точкой, которая всегда равна O (n ^ 2).
3. Также выполните поиск по «пространственному соединению», например, алгоритм TOUCH находит все парные точки в пределах максимального расстояния. Но вы можете достичь аналогичной производительности с хорошим универсальным многомерным индексом (я могу порекомендовать один, если хотите).
Ответ №1:
Один из подходов, который может помочь, — это вычислить сегмент для каждой точки как:
int(x/t),int(y/t)
т. е. точки (0.1,0.9), (0.5,0.5), (0.8,0.2) все они попадут в одно и то же ведро.
Поместите все точки в эти сегменты, затем повторите итерацию по точкам снова.
Причина такой организации заключается в том, что вам нужно только сопоставить точку с точками в том же сегменте или в 8 соседних сегментах.
В плохом случае это все равно может быть O (n ^ 2) (например, если все точки находятся в пределах t друг от друга), но в некоторых случаях это может помочь.