Существует ли структура данных, которая позволяет эффективно находить точки, близкие друг к другу?

Question

Я ищу структуру данных.
Допустим, у вас есть n очков p: = (x, y) с x, y ∈ [-128, 128]
Теперь вы инициализируете структуру данных и добавляете все n указывает на это.
Теперь для любой точки вы хотите легко найти любые точки, близкие к ней.
Точнее:
Укажите радиус r <1 и точку p. <br>Требуется функция F, которая выводит (несортированный) список всех точек q с d (p, q) Теперь я ищу структуру данных, которая позволяет оптимизировать эту функцию (стандартный алгоритм в O (n), вы можете получить что-то лучше?)
Я был бы рад получить ответ :)

Для людей, которые знают свое дело и хотят помочь еще дальше:
Скажите, что точки перемещаются во время интервалов (с максимальным расстоянием a <2). <br>Во время каждого интервала F вызывается для каждой точки (n- раз), теперь мы хотим расширить оптимизацию, чтобы после каждого интервала функция F была столь же эффективной.
Итак, нам нужна функция G, которая восстанавливает структуру данных.
G вызывается один раз, а F вызывается n раз. Мы хотим, чтобы O (G) + n * O (F)

В худшем случае нет места для улучшений, поэтому мы делаем предположение, что в каждом интервале для каждой точки p, по крайней мере, 50% всех точек находятся за пределами радиуса, указанного для функции F

Приведенные выше значения являются произвольными и должны заменяться любым другим числом. Я выбрал эти числа, чтобы проблему было легче понять, в дополнении x и y - числа с плавающей запятой.

Я хотел бы получить ответ, который укажет мне на другую статью, статью в Википедии или любую другую источник, который имел ту же или похожую проблему. Я действительно ожидаю, что никто не проведет весь день, пытаясь объяснить мне структуру данных;)

В любом случае, вся помощь приветствуется. Большое спасибо.

Answer 1

Эта проблема напоминает мне симуляцию частиц (в которой были подобные проблемы, как вы описали), которую я написал некоторое время go. Я нашел структуру данных, которая позволяет (с несколькими незначительными отклонениями на практике и при условии, что вы выбираете большое количество кусков) для сложности O (n).

Вы можете разделить имеющееся у вас двухмерное пространство на небольшой прямоугольник angular (я думаю, квадраты - лучшие в вашем случае) куски (с длиной стороны больше r).

Тогда вам нужно O(n) время, чтобы отсортировать точки по этим кускам.

Пусть k будет общим количеством кусков, которое у вас есть.

Тогда для нахождения всех точек, находящихся в пределах радиуса r для каждой точки, потребуется O(n*(n/k)) = O(n²/k), где n / k - приблизительное количество точек внутри каждого куска (при условии регулярного распределения, которое было верно для моделирования частиц, хотя не уверен в вашей проблеме). Имейте в виду, что для каждой точки вам также необходимо взглянуть на 8 соседних блоков!

Тогда у вас также есть дополнительный O(k), что объясняется тем фактом, что вам нужно перебирать фрагменты для доступа к элементам.

Таким образом, общая структура данных имеет сложность O(n²/k + n + k). Теперь, чтобы найти соотношение между n и оптимальным k, вы должны найти минимумы функции f(k) = a*n²/k + b*n + c*k, что можно сделать, найдя производную и установив ее равной нулю:

f'(k) = -an²/k² + c = 0 → n²/k² = c/a = constant → n пропорционально k, и поэтому, если k можно выбрать оптимальным:

O(n²/k + n + k) = O(n²/n + n+ n) = O(n)

Наихудший случай, конечно, все еще O(n²), когда k = 1

Answer 2

Существует много хороших структур данных, которые можно использовать для эффективного решения проблемы в двух измерениях. Структура данных дерева kd позволяет вам довольно быстро искать все точки в прямоугольнике по сравнению со стандартным линейным поиском при условии, что точки распределены более или менее случайным образом. Структура данных quadtree аналогичным образом поддерживает этот вид поиска. R-деревья были бы другим вариантом, хотя они в первую очередь оптимизированы для случаев, когда у вас есть огромное количество точек и вы хотите эффективно хранить информацию на диске.

Я помню, что в худшем случае все эти подходы принимают время O (n), но только с патологически выбранными входами. Для входов, которые имеют «разумные» распределения, время выполнения этих алгоритмов, как правило, намного лучше, поэтому их широко используют.

Надеюсь, это поможет!