Изменения

{{Лемма

|statement=

|proof=

Сторона квадрата на глубине <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_2(s \sqrt 2 / c) = \log_2 (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>\log_2 (s / c) + 1/2</tex>, из чего следует утверждение леммы (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).