Изменения

Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>log\log_2(s / c) + 3/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.

Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq log\log_2(s \sqrt 2 / c) = log \log_2 (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>log \log_2 (s / c) + 1/2</tex>, из чего следует утверждение леммы (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).