Изменения

Skip quadtree позволяет отвечать на запрос всех точек, лежащих в прямоугольнике, окруженном <tex>\varepsilon</tex>-областью, за <tex>O(\log n + \varepsilon^{-1})</tex>. Алгоритм можно модифицировать для ответа на запрос точек в любой выпуклой фигуре. Обозначим наш прямоугольник R. Тогда <tex>\varepsilon</tex>-область {{---}} область E, охватывающая R, граница которой удалена от его сторон на <tex>\varepsilon</tex>. Данный прямоугольник R разбивает вершины на следующие классы:* in - внутренние, то есть лежащие внутри <tex>\varepsilon</tex>-области (1 на рисунке).* out - внешние, то есть лежащие вне прямоугольника R (2 на рисунке).* stabbing - пронзающие, пересекающие R, но не являющие внутренними (3 на рисунке). Для вершин из классов in и out ответ на запрос находится тривиально, сложность представляют вершины из класса stabbing. Зная их все, мы можем ответить на запрос за <tex>O(|B|D_T)</tex>, где B - множество пронзающих вершин, D_T - глубина нашего дерева T.  Мощность множества B может составлять O(n), так как пронзающие вершины могут быть вложены друг в друга, тогда как нам достаточно рассмотреть только наименьшую из вложенных вершин. Назовем пронзающую вершину критической, если для каждого из ее детей выполняется одно из двух условий:* ребенок не является пронзающей вершиной.* ребенок является пронзающим, но содержит меньшую часть E, чем рассматриваемая вершина.  На рисунке среди вершин 3, 4, 5, 6 только 5 является критической.