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