355
правок
Изменения
Нет описания правки
* Шаг 1. Удалим некоторое количество неграничных и независимых (попарно несмежных друг с другом) вершин и инцидентные им ребра (от выбора этого множества напрямую зависит оптимальность алгоритма).
* Шаг 2. Построить триангуляцию получившихся в результате шага 1 многоугольников.
Таким образом $S_{h(N)}$ состоит из одного треугольника. Заметим, что все триангуляции имеют одну общую границу, так как удаляются только внутренние узлы. Далее, будем обозначать все треугольники как $R$, а также будем говорить, что треугольник $R_ij$ принадлежит триангуляции $S_i$, если
он был создан на шаге (2) при построении этой триангуляции.
Теперь построим структуру данных $T$ для поиска. Эта структура представляет собой направленный ацикличный граф, вершинами которого будут наши треугольники. Определим эту структуру следующим образом: из треугольника $R_k$ будет вести ребро в треугольник $R_$$$, если при построении $S_i$ из $S_{i-1}$ мы имеем
* $R_j$ удалятся из $S_{i - 1}$ на шаге (1)
* $R_k$ создается в $S_{i}$ на шаге (2)
* $R_j \cap R_k \not \bigcirc$
</wikitex>
