Изменения
→Запрос точек в прямоугольнике
|proof=
Рассмотрим квадродерево <tex>T</tex>, состоящее только из критических вершин.
Назовем вершину дерева <tex>T</tex> ветвящейся, если у нее есть как минимум два ребенка. Не ветвящаяся вершина {{---}} лист или такая, что ее единственный ребенок содержит меньшую часть <tex>\varepsilon</tex>-области. Две вершины квадродерева покрывают разные области <tex>R</tex> (не обязательно непересекающиеся), только если они пересекают границу <tex>R</tex> в разных местах. Поэтому они покрывают разные области <tex>E</tex>.
Таким образом, для каждой неветвящейся вершины существует уникальная область <tex>E</tex>, покрываемая только этой вершиной и никакой другой. Объем этой области составляет <tex>\Omega(1)</tex>, так как каждая критическая вершина {{---}} гиперкуб.
