419
правок
Изменения
Нет описания правки
== Одномерный случай ==
[[Файл:Line_with_dots_and_segment.png]]<br>
Задача тривиальна — нужно оставить только те точки, которые находятся лежат между началом и концом отрезка.
На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.
}
Алгоритм работает за <tex>O(\log n+ T)</tex>, где <tex>T</tex> - количество точек в ответе.<br> '''Примечание:''' Если задача сформулирована так, что нужно вывести все искомые точки, то запрос не может выполняться быстрее, чем за <tex>O(T)</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> — размерность пространства.
