Ортогональный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сбалансированное дерево поиска)
(не показано 38 промежуточных версий 3 участников)
Строка 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>
 +
Задача тривиальна — нужно оставить только те точки, которые лежат между началом и концом отрезка.
  
Данная задача решается с помощью функций из STL - upper_bound и lower_bound.
+
На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.
  
 
lower_bound возвращает итератор на первый элемент, больший либо равный данного. <br>
 
lower_bound возвращает итератор на первый элемент, больший либо равный данного. <br>
Строка 13: Строка 14:
 
Рассмотрим на примере:
 
Рассмотрим на примере:
  
[[Файл:Upper_bound_and_lower_bound1.png|600px]]
+
[[Файл:Upper_bound_and_lower_bound2.png|600px]]
  
 
Код реализации:
 
Код реализации:
Строка 22: Строка 23:
 
  }
 
  }
  
== Сбалансированное дерево поиска ==
+
Алгоритм работает за <tex>O(\log n + T)</tex>, где <tex>T</tex> - количество точек в ответе.<br>
  
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
+
'''Примечание:''' Если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за <tex>O(T)</tex>. Однако, далеко не во всех задачах ортогонального поиска нужно получать все точки в явном виде. Поэтому далее время, необходимое для вывода полного ответа, будет опускаться в оценке времени запроса.
 +
 
 +
== Двумерный случай ==
 +
 
 +
Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
  
 
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. <br>Рассмотрим на примере:<br>
 
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. <br>Рассмотрим на примере:<br>
 
[[Файл:ortog_search_tree.png|600px]]<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_{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>x</tex>-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как <tex>v_l</tex> и <tex>v_r</tex>.  
 
# Добавим в искомое множество их наименьшего общего предка <tex>v_n</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_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>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
 
# Повторим процесс для пути <tex>v_r \to v_n</tex>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
В итоге, в множество мы добавим <tex>O(\log n)</tex> вершин и <tex>O(\log n)</tex> поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, <tex>y</tex>-координата которых не находится в прямоугольнике запроса. Для точек это сделать просто — нужно вручную проверить, лежит ли <tex>y</tex>-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
+
Пример процесса показан на иллюстрации:<br>
{{TODO| t=запилить красивую и понятную картинку}}
+
[[Файл: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> памяти.
  
Каждая из функций <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>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> на занимаемую память.
Строка 42: Строка 49:
 
Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]].
 
Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]].
  
== Прошитые отсортированные массивы ==
+
== Ускорение запроса ==
Для ускорения запроса можно "прошить" дерево поиска, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. Тогда для выполнения завершающей фазы поиска нам достаточно будет посчитать <tex>upper\_bound()</tex> и <tex>lower\_bound()</tex> только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам от массива-предка за <tex>O(1)</tex>. Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</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> — размерность пространства.
{{TODO| t=здесь тоже надо что-нибудь нарисовать}}
 
 
 
== Квадро дерево ==
 
  
== Инкрементальное квадро дерево ==
+
[[Категория: Вычислительная геометрия]]

Версия 15:18, 16 июня 2012

Пусть задано множество точек [math]S[/math] из пространства [math]\mathbb R^n[/math]. Пусть односвязная область [math]R \subset \mathbb R^n[/math] такова, что её границы ортогональны координатным прямым. Требуется определить множество точек [math]S' \subset S[/math], лежащих в области [math]R[/math].

Одномерный случай

Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке.

Line with dots and segment.png
Задача тривиальна — нужно оставить только те точки, которые лежат между началом и концом отрезка.

На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.

lower_bound возвращает итератор на первый элемент, больший либо равный данного.
upper_bound возвращает итератор на первый элемент множества со значением, большим данного.

Рассмотрим на примере:

Upper bound and lower bound2.png

Код реализации:

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);
}

Алгоритм работает за [math]O(\log n + T)[/math], где [math]T[/math] - количество точек в ответе.

Примечание: Если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за [math]O(T)[/math]. Однако, далеко не во всех задачах ортогонального поиска нужно получать все точки в явном виде. Поэтому далее время, необходимое для вывода полного ответа, будет опускаться в оценке времени запроса.

Двумерный случай

Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.

Для этого возьмем любое сбалансированное дерево поиска и наполним его точками [math](x, y)[/math] из множества. В качестве ключа будет использоваться [math]x[/math]-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по [math]y[/math]-координате массив точек, которые содержатся в соответствующем поддереве.
Рассмотрим на примере:
Ortog search tree.png
Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек, находящихся в заданном прямоугольнике [math][x_{min}, x_{max}] \times [y_{min}, y_{max}][/math]. Для начала, найдем в дереве те точки, [math]x[/math]-координата которых лежит в интервале [math][x_{min}, x_{max}][/math]. Сделаем это следующим образом:

  1. Найдем в дереве поиска вершины с минимальной и максимальной [math]x[/math]-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как [math]v_l[/math] и [math]v_r[/math].
  2. Добавим в искомое множество их наименьшего общего предка [math]v_n[/math].
  3. Для каждой из промежуточных вершин [math]v_i[/math] на восходящем пути [math]v_l \to v_n[/math] зафиксируем, из какого ребенка мы поднялись в вершину [math]v_i[/math]. Если мы поднялись из левого сына, то добавим в искомое множество саму вершину [math]v_i[/math], а также множество точек, находящихся в поддереве правого сына вершины [math]v_i[/math]. Если же мы поднялись из правого сына, то не добавляем ничего.
  4. Повторим процесс для пути [math]v_r \to v_n[/math]. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.

Пример процесса показан на иллюстрации:
Ortog search tree2.png
В итоге, в множество мы добавим [math]O(\log n)[/math] вершин и [math]O(\log n)[/math] поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, [math]y[/math]-координата которых не лежит в интервале [math][y_{min}, y_{max}][/math]. Для точек это сделать просто — нужно вручную проверить, лежит ли [math]y[/math]-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию [math]range{\_}search(y_{min}, y_{max})[/math]. Все полученные таким образом точки и будут составлять ответ.
Каждая из функций [math]range{\_}search(y_{min}, y_{max})[/math] будет работать в худшем случае за [math]O(\log n)[/math], отсюда получаем итоговое время выполнения запроса [math]O(\log^2 n)[/math]. Что касается памяти, то в сбалансированном дереве поиска [math]O(\log n)[/math] слоев, а каждый слой хранит массивы, содержащие в сумме ровно [math]n[/math] точек, соответственно вся структура в целом занимает [math]O(n\log n)[/math] памяти.

Обобщение для p-мерного пространства

Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из [math]p[/math]-мерного пространства, каждая из которых представляется как [math]n[/math] координатных чисел: [math](\xi_1, \xi_2, ... , \xi_p)[/math]. Тогда, строя дерево поиска по координате [math]\xi_i[/math], в каждой вершине будем хранить другое дерево поиска с ключом [math]\xi_{i+1}[/math], составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате [math]\xi_{p-1}[/math], уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату [math]\xi_{p}[/math] дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на [math]\log n[/math]. Отсюда, получаем оценку [math]O(\log^{p} n)[/math] на время запроса и [math]O(n\log^{p-1} n)[/math] на занимаемую память.

Такой же результат можно получить с помощью сжатого многомерного дерева отрезков.

Ускорение запроса

Для ускорения запроса можно "прошить" дерево поиска по предпоследней координате, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент [math](x, y)[/math] массива-предка соединим с элементами [math]upper\_bound(y)[/math] и [math]lower\_bound(y)[/math] каждого массива-ребенка. Ниже представлен пример соединения корня с его левым сыном:
Ortog search tree3.png
Для выполнения завершающей фазы поиска нам достаточно будет посчитать [math]upper\_bound()[/math] и [math]lower\_bound()[/math] только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей [math]v_l \to v_n[/math] или [math]v_r \to v_n[/math]. Отсюда следует, что число спусков оценивается как [math]O(length(v_l \to v_n) + length(v_r \to v_n)) = O(\log n)[/math].
Таким образом, поиск теперь будет выполняться за [math]O(\log^{p-1} n)[/math], где [math]p[/math] — размерность пространства.