355
правок
Изменения
Нет описания правки
* $R_j$ удалятся из $S_{i - 1}$ на шаге (1)
* $R_k$ создается в $S_{i}$ на шаге (2)
* $R_j \cap R_k \not \bigcirc$
Очевидно, что треугольники из $S_1$ (и только они) не имеют исходящих ребер.
===Поиск===
<wikitex> После построения структуры легко понять, как в ней происходит поиск. Элементарной операцией здесь является определение принадлежности треугольнику. Очевидно, что она выполняется константное время. Сначала мы локализуемся в треугольнике $S_1$. После этого мы строим путь от корневой вершины до листа следующим образом: находясь в какой-либо вершине $z$, просмотрим всех ее детей на принадлежность точки соответствующему треугольнику и, так как точка может находиться лишь в одном треугольнике конкретной триангуляции, перейдем в эту вершину, и продолжим поиск.
Этот поиск также можно рассматривать как последовательную локализацию в триангуляциях $S_1, \dots, S_{h(N)}$, откуда и происходит название самого метода.
