Есть ли какой-либо алгоритм лучше, чем O (n^2), чтобы соединить любые две точки по прямой, если их расстояние меньше постоянной t?Подключите любые две точки в двумерном пространстве
Я думаю о сортировке точек в соответствии с их координатой x, а затем ищет другую точку внутри [x-t, x + t]. Но в худшем случае все еще O (n^2). Есть идеи? У нас есть какая-то специальная структура данных для ускорения?
Один подход, который может помочь, чтобы вычислить ведро для каждой точки, как:
int(x/t),int(y/t)
т.е. точек (0.1,0.9), (0.5,0.5), (0.8,0.2) будет все вдаваться в такой же ковш.
Поместите все точки в эти ведра, а затем снова проведите по пунктам.
Причина для этой организации заключается в том, что вам нужно только проверить точку на точки в том же ковше или в 8 соседних ведрах.
В плохом случае это все равно может быть O (n^2) (например, если все точки находятся внутри t друг друга), но это может помочь в некоторых случаях.
Поиск "ближайшая пара проблем". –
Есть ли ограничение на t? В противном случае, если все точки находятся внутри t друг друга, вам нужно будет соединить каждую точку с любой другой точкой, которая всегда O (n^2). – TilmannZ
Кроме того, поиск «пространственного соединения», например, алгоритм [TOUCH] (https://infoscience.epfl.ch/record/186338/files/sigfp132-nobari_1.pdf) находит все точки пар на максимальном расстоянии. Но вы можете добиться аналогичной производительности с хорошим универсальным многомерным индексом (я могу порекомендовать его, если хотите). – TilmannZ