Ортогональный поиск — различия между версиями
Glukos (обсуждение | вклад) (→Прошитые отсортированные массивы) |
м (rollbackEdits.php mass rollback) |
||
(не показано 57 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | Пусть задано множество точек <tex>S</tex> из пространства <tex>\mathbb R^n</tex>. Пусть односвязная область <tex>R \subset \mathbb R^n</tex> такова, что её границы ортогональны координатным прямым. Требуется определить множество точек <tex>S' \subset S</tex>, лежащих в области <tex>R</tex>. |
+ | == Одномерный случай == | ||
− | Пусть дана прямая с точками на ней и отрезок | + | Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке. |
− | [[Файл:Line_with_dots_and_segment.png]] | + | [[Файл:Line_with_dots_and_segment.png]]<br> |
+ | Задача тривиальна — нужно оставить только те точки, которые лежат между началом и концом отрезка. | ||
− | + | На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound. | |
lower_bound возвращает итератор на первый элемент, больший либо равный данного. <br> | lower_bound возвращает итератор на первый элемент, больший либо равный данного. <br> | ||
Строка 12: | Строка 14: | ||
Рассмотрим на примере: | Рассмотрим на примере: | ||
− | [[Файл: | + | [[Файл:Upper_bound_and_lower_bound2.png|600px]] |
Код реализации: | Код реализации: | ||
Строка 21: | Строка 23: | ||
} | } | ||
− | + | Алгоритм работает за <tex>O(\log n + T)</tex>, где <tex>T</tex> - количество точек в ответе.<br> | |
− | + | '''Примечание:''' Если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за <tex>O(T)</tex>. Однако, далеко не во всех задачах ортогонального поиска нужно получать все точки в явном виде. Поэтому далее время, необходимое для вывода полного ответа, будет опускаться в оценке времени запроса. | |
− | + | == Двумерный случай == | |
− | |||
− | |||
− | |||
− | + | Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике. | |
− | Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex> | + | Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. <br>Рассмотрим на примере:<br> |
+ | [[Файл:ortog_search_tree.png|600px]]<br> | ||
+ | Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек, находящихся в заданном прямоугольнике <tex>[x_{min}, x_{max}] \times [y_{min}, y_{max}]</tex>. Для начала, найдем в дереве те точки, <tex>x</tex>-координата которых лежит в интервале <tex>[x_{min}, x_{max}]</tex>. Сделаем это следующим образом: | ||
+ | # Найдем в дереве поиска вершины с минимальной и максимальной <tex>x</tex>-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как <tex>v_l</tex> и <tex>v_r</tex>. | ||
+ | # Добавим в искомое множество их наименьшего общего предка <tex>v_n</tex>. | ||
+ | # Для каждой из промежуточных вершин <tex>v_i</tex> на восходящем пути <tex>v_l \to v_n</tex> зафиксируем, из какого ребенка мы поднялись в вершину <tex>v_i</tex>. Если мы поднялись из левого сына, то добавим в искомое множество саму вершину <tex>v_i</tex>, а также множество точек, находящихся в поддереве правого сына вершины <tex>v_i</tex>. Если же мы поднялись из правого сына, то не добавляем ничего. | ||
+ | # Повторим процесс для пути <tex>v_r \to v_n</tex>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына. | ||
+ | Пример процесса показан на иллюстрации:<br> | ||
+ | [[Файл:ortog_search_tree2.png|700px]]<br> | ||
+ | В итоге, в множество мы добавим <tex>O(\log n)</tex> вершин и <tex>O(\log n)</tex> поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, <tex>y</tex>-координата которых не лежит в интервале <tex>[y_{min}, y_{max}]</tex>. Для точек это сделать просто — нужно вручную проверить, лежит ли <tex>y</tex>-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ. | ||
+ | <br>Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой хранит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти. | ||
+ | |||
+ | == Обобщение для p-мерного пространства == | ||
+ | |||
+ | Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex>p</tex>-мерного пространства, каждая из которых представляется как <tex>n</tex> координатных чисел: <tex>(\xi_1, \xi_2, ... , \xi_p)</tex>. Тогда, строя дерево поиска по координате <tex>\xi_i</tex>, в каждой вершине будем хранить другое дерево поиска с ключом <tex>\xi_{i+1}</tex>, составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате <tex>\xi_{p-1}</tex>, уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату <tex>\xi_{p}</tex> дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на <tex>\log n</tex>. Отсюда, получаем оценку <tex>O(\log^{p} n)</tex> на время запроса и <tex>O(n\log^{p-1} n)</tex> на занимаемую память. | ||
Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]]. | Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]]. | ||
− | == | + | == Ускорение запроса == |
− | Для ускорения запроса можно "прошить" дерево поиска, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. | + | Для ускорения запроса можно "прошить" дерево поиска по предпоследней координате, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. Ниже представлен пример соединения корня с его левым сыном:<br>[[Файл:ortog_search_tree3.png]]<br>Для выполнения завершающей фазы поиска нам достаточно будет посчитать <tex>upper\_bound()</tex> и <tex>lower\_bound()</tex> только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей <tex>v_l \to v_n</tex> или <tex>v_r \to v_n</tex>. Отсюда следует, что число спусков оценивается как <tex>O(length(v_l \to v_n) + length(v_r \to v_n)) = O(\log n)</tex>. <br>Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</tex> — размерность пространства. |
− | |||
− | |||
− | + | [[Категория: Вычислительная геометрия]] |
Текущая версия на 19:19, 4 сентября 2022
Пусть задано множество точек
из пространства . Пусть односвязная область такова, что её границы ортогональны координатным прямым. Требуется определить множество точек , лежащих в области .Одномерный случай
Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке.
Задача тривиальна — нужно оставить только те точки, которые лежат между началом и концом отрезка.
На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.
lower_bound возвращает итератор на первый элемент, больший либо равный данного.
upper_bound возвращает итератор на первый элемент множества со значением, большим данного.
Рассмотрим на примере:
Код реализации:
template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out) { return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out); }
Алгоритм работает за
Примечание: Если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за
. Однако, далеко не во всех задачах ортогонального поиска нужно получать все точки в явном виде. Поэтому далее время, необходимое для вывода полного ответа, будет опускаться в оценке времени запроса.Двумерный случай
Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками
Рассмотрим на примере:
Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек, находящихся в заданном прямоугольнике . Для начала, найдем в дереве те точки, -координата которых лежит в интервале . Сделаем это следующим образом:
- Найдем в дереве поиска вершины с минимальной и максимальной -координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как и .
- Добавим в искомое множество их наименьшего общего предка .
- Для каждой из промежуточных вершин на восходящем пути зафиксируем, из какого ребенка мы поднялись в вершину . Если мы поднялись из левого сына, то добавим в искомое множество саму вершину , а также множество точек, находящихся в поддереве правого сына вершины . Если же мы поднялись из правого сына, то не добавляем ничего.
- Повторим процесс для пути . Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
Пример процесса показан на иллюстрации:
В итоге, в множество мы добавим вершин и поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, -координата которых не лежит в интервале . Для точек это сделать просто — нужно вручную проверить, лежит ли -координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию . Все полученные таким образом точки и будут составлять ответ.
Каждая из функций будет работать в худшем случае за , отсюда получаем итоговое время выполнения запроса . Что касается памяти, то в сбалансированном дереве поиска слоев, а каждый слой хранит массивы, содержащие в сумме ровно точек, соответственно вся структура в целом занимает памяти.
Обобщение для p-мерного пространства
Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из
-мерного пространства, каждая из которых представляется как координатных чисел: . Тогда, строя дерево поиска по координате , в каждой вершине будем хранить другое дерево поиска с ключом , составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате , уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на . Отсюда, получаем оценку на время запроса и на занимаемую память.Такой же результат можно получить с помощью сжатого многомерного дерева отрезков.
Ускорение запроса
Для ускорения запроса можно "прошить" дерево поиска по предпоследней координате, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент
Для выполнения завершающей фазы поиска нам достаточно будет посчитать и только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей или . Отсюда следует, что число спусков оценивается как .
Таким образом, поиск теперь будет выполняться за , где — размерность пространства.