Изменения
→Запрос точек в прямоугольнике
Задача: нам дается прямоугольник, нужно выдать все точки, лежащие в нем.
Реализация запроса на сжатом квадродереве занимает <tex>O\Omega(\sqrt{n} + k)</tex> времени. Используем skip quadtree для ускорения поиска. Для этого ослабим условие задачи, тогда skip quadtree позволит очень быстро (асимптотически) отвечать на такие запросы.
Ослабление: расширим данный прямоугольник на <tex>\varepsilon</tex>.
Количество ''критически''х вершин на нулевом уровне дерева равно <tex>O(\varepsilon^{-1})</tex>.
|proof=
Для квадратов с длиной стороны <tex>\varepsilon</tex> верно, что они либо <tex>\mathrm{in}</tex>, либо <tex>\mathrm{out}</tex>, то есть <tex>\mathrm{stabbing}</tex> квадратов вершин с длиной стороны <tex>\varepsilon</tex> такой стороной не бывает, как и с длиной стороны со стороной меньше <tex>\varepsilon</tex>.
Все точки, содержащиеся в skip quadtree, находятся внутри какого-то прямоугольника, значит, длина его стороны {{---}} константа. Поэтому длина стороны области пересечения запрашиваемого прямоугольника со skip quadtree {{---}} это тоже константа. Тогда длина стороны запрашиваемого прямоугольника {{---}} <tex>O(1)</tex>.
''Пронзающих'' вершин c длиной стороны <tex>\varepsilon</tex>, области которых не пересекаются, может быть <tex>O(\varepsilon^{-1})</tex>, тогда всего их может быть <tex>\varepsilon^{-1} + \genfrac{}{}{}{0}{1}{2} \cdot \varepsilon^{-1} + \genfrac{}{}{}{0}{1}{4} \cdot \varepsilon^{-1} + ...\dots</tex> = <tex>O(\varepsilon^{-1})</tex>.
''Критических'' вершин не больше, чем ''пронзающих'', так что их тоже <tex>O(\varepsilon^{-1})</tex>.
}}
