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

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

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

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


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

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


optimization multidimensional-array points data-structures time-complexity
person Ta1sty    schedule 23.03.2020    source источник
comment
Думаю, вы получите более точные ответы здесь: math.stackexchange.com/questions/tagged/asymptotics   -  person J'e    schedule 23.03.2020

Ответы (2)


arrow_upward
1
arrow_downward

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

Вы можете разделить имеющееся у вас двухмерное пространство на небольшие прямоугольные (я думаю, что квадраты лучше всего в вашем случае) куски (с длиной стороны больше 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

person QuantumDeveloper    schedule 23.03.2020
comment
Это решает мою проблему. Спасибо за объяснение. - person Ta1sty; 23.03.2020

arrow_upward
0
arrow_downward

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

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

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

person templatetypedef    schedule 23.03.2020