Пространственная структура данных для нахождения всех точек больше или меньше значения в каждом декартовом измерении

В настоящее время я работаю над проблемой оптимизации, которая требует нахождения всех точек, превышающих (или в некоторых случаях меньше) конкретную точку во всех кардинальных направлениях. Например, в 2D, мне может потребоваться найти все точки, которые удовлетворяют условию:

x > x* and y < y* 
for an arbitrary point (x*,y*)

(например, если синяя точка на графике ниже (x *, y *), мне нужны все точки в поле, определяемом синими пунктирными линиями).

Примечание. Мне нужно, чтобы это была N-мерная структура/поиск, так как моя фактическая проблема оптимизации имеет более двух целей, которые необходимо решить. Типичное пространство поиска будет порядка 1000-5000 точек и будет иметь от 2 до 5 измерений.

Есть ли какая-либо конкретная структура данных, хорошо подходящая для этой цели? Раньше я использовал kd-деревья для поиска ближайших соседей и всех точек в радиусе, однако в этом случае мне нужен направленный поиск. Похоже, что какая-то форма R-Tree может сделать трюк, где мой прямоугольник поиска будет идти от x *, y * до некоторых в значительной степени положительных и в значительной степени отрицательных значений соответственно. Есть ли лучшая структура данных, характерная для такого рода поиска?

Ответ 1

Из того, что я прочитал из ваших комментариев, вам задан набор точек P ₁,..., P _n и вы хотите найти для каждого точка P _i= (x ₁,..., x _d) число точек P _j= (y ₁,..., y _d) с x _k R _k y _k для всех k, где R _k является одним из (<, > ).

Одно наблюдение состоит в том, что вы можете сортировать точки по их первой координате и добавлять их в свою структуру данных в том порядке, в котором они становятся видимыми относительно этой координаты. Это удаляет одно измерение из вашей задачи поиска, поэтому в d-мерном случае ваша проблема теперь сводится к проблеме (d-1) -мерного ортогонального диапазона запросов. Эта оптимизация полностью не зависит от того, как вы фактически решаете запросы ортогонального диапазона, и сама по себе может сделать реализацию грубой силы более жизнеспособной.

Так как ваш точечный набор более или менее статичен (вы можете построить структуру данных в полном наборе точек, изначально установить счетчики всех узлов на ноль и затем "вставить" точки, включив их), вы можете использовать дерево диапазонов для решения запросов ортогонального диапазона. В тривиальной реализации это дает вам предварительную обработку O (n log ^d-2 n) и время запроса O (log ^d-2 n) со слегка улучшенной версией структура данных

Таким образом, общая стоимость одной фазы будет тогда O (n log ^d-2 n). Поскольку ваш n настолько мал, я не уверен, действительно ли это вас купит (это, вероятно, неразумно для 5-го случая, может быть, даже не для 4-го).

Если вы хотите пойти по этому маршруту, я могу порекомендовать лекции по структурам данных Erik Demaine, которые охватывают запросы ортогонального диапазона (в L03 и L04). Он также охватывает концептуально немного более простые полуоткрытые запросы, которые вам нужны, поэтому, возможно, это может быть реализовано с более низким постоянным коэффициентом.

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

Если ваши точки распределены достаточно случайным образом, вам, вероятно, удастся разделить точки на прямоугольные ведра O (n ^0,5). Вы можете подсчитать количество точек в ковше в O (1) и количество точек в ведре в O (n ^0,5), а реализация имеет очень низкие накладные расходы по сравнению с деревьями диапазона. В сочетании с сортировкой по одной координате это должно дать вам приличные ускорения. Это определенно то, что я постараюсь первым.