355
правок
Изменения
→Выбор множества удаляемых вершин
'''Свойство 2'''. Каждый треугольник $R_i \in S_i$ пересекается не более чем с $H$ треугольниками из $S_{i-1}$ и наоборот.
Первое свойство немедленно влечет за собой следствие, что $h(N) \le \left \lceil \log_{1/a}N \right \rceil = O(log N)$, поскольку при переходе от $S_{i-1} $ к $S_i$ удаляется по меньшей мере фиксированная доля вершин.
Также из этих свойств следует, что память для $T$ равна $O(N)$. Действительно, заметим, что эта память используется для хранения узлов и указателей на их потомков. Из [[Формула_Эйлера|теоремы Эйлера]] о плоских графах следует, что $S_i$ содержит $F_i < 2N_i$ треугольников. Число узлов в $T$, представляющих треугольники из $S_i$, не превосходит $F_i$ (только те треугольники, которые действительно принадлежат $S_i$, появляются на соответствующем «ярусе» $T$). Отсюда следует, что общее число узлов в $T$ меньше, чем
