Изменения
→О размерах сжатого квадродерева
Сжатое квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин и глубину <tex>O(n)</tex>.
|proof=
Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
* для <tex>n = 1</tex> это очевидно;
* пусть в квадродереве <tex>n > 1</tex> точек. Рассмотрим корень, у него обязательно должно быть хотя бы 2 непустых ребёнка. Если хотя бы один из детей является точкой, то остальные непустые дети являются деревьями, в которых суммарно не больше <tex>n - 1</tex> точек (и в каждом их меньше <tex>n</tex>). Значит, в них суммарно не больше <tex>n - 1</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше <tex>n</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами, то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самое, поскольку во всех поддеревьях будет меньше <tex>n</tex> точек (ибо их суммарно <tex>n</tex> и везде есть хотя бы одна, так как дети непустые).
