Изменения
→Запрос точек в прямоугольнике
==Запрос точек в прямоугольнике==
Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.
Реализация запроса на сжатом квадродереве занимает <tex>O(\sqrt{n} + k)</tex> времени. Используем skip quadtree для ускорения поиска. Для этого ослабим условие задачи, тогда skip quadtree позволит очень быстро (асимптотически) отвечать на такие запросы.
Ослабление: расширим данный прямоугольник на <tex>\varepsilon</tex>.
Тогда в ответ могут попасть точки не из данного прямоугольника, но лежащие внутри <tex>\varepsilon</tex>-области. В большинстве практических задач данное ослабление не ухудшит конечный результат, а только ускорит процесс.
Skip quadtree позволяет отвечать на запрос всех точек, лежащих в прямоугольнике, окруженном <tex>\varepsilon</tex>-областью, за <tex>O(\varepsilon^{-1} \cdot \log n + k)</tex>, где <tex>k</tex> {{---}} число точек в ответе. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре.
[[Файл:Skip_quadtree_rect.png|right|400px]]
Данный прямоугольник <tex>R</tex> разбивает вершины на следующие классы:
* <tex>\mathrm{in}</tex> {{---}} внутренние, то есть лежащие внутри <tex>\varepsilon</tex>-области (1 и 6 на рисунке).
* <tex>\mathrm{out}</tex> {{---}} внешние, то есть лежащие вне прямоугольника <tex>R</tex> (2 на рисунке).
* <tex>\mathrm{stabbing}</tex> {{---}} пронзающие, пересекающие <tex>R</tex>, но не являющие внутренними (3 , 4 и 5 на рисунке).
Для вершин из классов <tex>\mathrm{in}</tex> и <tex>\mathrm{out}</tex> ответ на запрос находится тривиально, сложность представляют вершины из класса <tex>\mathrm{stabbing}</tex>. Зная их все, мы можем ответить на запрос.
