Изменения
→Сбалансированное дерево поиска
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <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>.
