Поиск диапазона

Симплексный поиск диапазона.

В информатике состоит проблема поиска диапазона из обработки набора S объектов, чтобы определить, какие объекты из S пересекаются с объектом запроса, называемым диапазоном . Например, если S — набор точек, соответствующих координатам нескольких городов, найдите подмножество городов в заданном диапазоне широт и долгот .

Проблема поиска диапазона и структуры данных , которые ее решают, являются фундаментальной темой вычислительной геометрии . Приложения проблемы возникают в таких областях, как географические информационные системы (ГИС), системы автоматизированного проектирования (САПР) и базы данных .

Вариации

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

• Типы объектов: Алгоритмы зависят от того, состоит ли S из точек , линий , отрезков линий , прямоугольников , многоугольников .... Самыми простыми и наиболее изученными объектами для поиска являются точки.
• Типы диапазонов. Диапазоны запроса также необходимо выбирать из заранее определенного набора. Некоторые хорошо изученные наборы диапазонов и названия соответствующих задач — это прямоугольники, выровненные по осям (поиск ортогонального диапазона), симплексы , полупространства и сферы / круги .
• Типы запросов. Если необходимо сообщить список всех объектов, пересекающих диапазон запроса, проблема называется отчетом о диапазоне , а запрос называется запросом отчета . Иногда требуется только количество объектов, пересекающих диапазон. В этом случае задача называется подсчетом диапазона , а запрос называется подсчетным запросом . Запрос на пустоту сообщает, существует ли хотя бы один объект, пересекающий диапазон. В полугрупповом варианте полугруппа коммутативная . ( S указывается ,+), каждой точке присваивается вес из S и требуется сообщить полугрупповую сумму весов точек, пересекающих диапазон
• Поиск в динамическом диапазоне и поиск в статическом диапазоне: в статических настройках набор S известен заранее. При динамической настройке объекты могут быть вставлены или удалены между запросами.
• Автономный поиск по диапазону: заранее известен как набор объектов, так и весь набор запросов.

Структуры данных

Поиск ортогонального диапазона

Запрос двумерного ортогонального диапазона. В этом случае запрос отчета о диапазоне вернет две точки в кружках, запрос подсчета диапазона вернет 2, а запрос на пустоту вернет false.

При поиске ортогонального диапазона набор S состоит из $n$ указывает на $d$ измерения, а запрос состоит из интервалов в каждом из этих измерений. Таким образом, запрос состоит из многомерного прямоугольника, выровненного по оси . С выходным размером $k$, Джон Бентли использовал дерево kd для достижения (в нотации Big O ) $O(n)$ пространство и $O{\big (}n^{1-{\frac {1}{d}}}+k{\big )}$ время запроса. Бентли также предложил использовать деревья диапазонов , что позволило сократить время запроса. $O(\log ^{d}n+k)$ но увеличилось пространство для $O(n\log ^{d-1}n)$. Дэн Уиллард использовал нисходящие указатели — особый случай дробного каскадирования, чтобы еще больше сократить время запроса. $O(\log ^{d-1}n+k)$.

Хотя вышеуказанные результаты были достигнуты в модели указателя , дальнейшие улучшения были сделаны в словном ОЗУ модели вычислений в в малых размерностях (2D, 3D, 4D). Бернар Шазель использовал сжатие деревьев диапазонов для достижения $O(\log n)$ время запроса и $O(n)$ место для подсчета дальности. Джозеф ДжаДжа и другие позже улучшили время запроса до $O\left({\dfrac {\log n}{\log \log n}}\right)$ для подсчета диапазона, который соответствует нижней границе и, таким образом, является асимптотически оптимальным .

По состоянию на 2015 год лучшие результаты (в малых измерениях (2D, 3D, 4D)) для отчетов о диапазонах, найденные Тимоти М. Чаном , Каспером Ларсеном и Михаем Патрашку , также с использованием сжатых деревьев диапазонов в модели вычислений Word RAM: одно из следующих:

• $O(n)$ космос, $O(\log ^{\epsilon }n+k\log ^{\epsilon }n)$ время запроса
• $O(n\log \log n)$ космос, $O(\log \log n+k\log \log n)$ время запроса
• $O(n\log ^{\epsilon }n)$ космос, $O(\log \log n+k)$ время запроса

В ортогональном случае, если одна из границ равна бесконечности , запрос называется трёхсторонним. Если две границы бесконечны, запрос является двусторонним, а если ни одна из границ не бесконечна, то запрос является четырехсторонним.

Поиск в динамическом диапазоне

В то время как при поиске в статическом диапазоне набор S известен заранее, поиск в динамическом диапазоне, вставка и удаление точек разрешены. В инкрементной версии проблемы разрешены только вставки, тогда как в декрементной версии разрешены только удаления. Для ортогонального случая Курт Мельхорн и Стефан Нэхер создали структуру данных для поиска в динамическом диапазоне, которая использует динамическое дробное каскадирование для достижения $O(n\log n)$ пространство и $O(\log n\log \log n+k)$ время запроса. Как инкрементные, так и декрементные версии проблемы могут быть решены с помощью $O(\log n+k)$ время запроса, но неизвестно, можно ли выполнить общий поиск в динамическом диапазоне за это время запроса.

Поиск цветового диапазона

Задача подсчета цветных диапазонов рассматривает случай, когда точки имеют категориальные атрибуты. Если категории рассматриваются как цвета точек в геометрическом пространстве, то запрос заключается в том, сколько цветов встречается в определенном диапазоне. Просенджит Гупта и другие описали структуру данных в 1995 году, которая позволяла решать двумерный подсчет ортогональных цветных диапазонов в $O(n^{2}\log ^{2}n)$ пространство и $O(\log ^{2}n)$ время запроса.

Приложения

Помимо рассмотрения в вычислительной геометрии , поиске диапазона и, в частности, поиске ортогонального диапазона, он имеет приложения для запросов диапазона в базах данных . Поиск по цветовому диапазону также используется и мотивируется поиском по категориальным данным. Например, определение строк в базе данных банковских счетов, которые представляют людей в возрасте от 25 до 40 лет и имеющих от 10 000 до 20 000 долларов США, может быть проблемой отчетности по ортогональному диапазону, где возраст и деньги являются двумя измерениями.

См. также

• Дерево диапазона
• Запрос диапазона

Дальнейшее чтение

• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000), Вычислительная геометрия (2-е изд.), Берлин: Springer-Verlag, ISBN  3-540-65620-0
• Матушек, Иржи (1994), «Поиск геометрического диапазона» , ACM Computing Surveys , 26 (4): 421–461, doi : 10.1145/197405.197408 , S2CID   17729301 .