355
правок
Изменения
→Структура данных
===Структура данных===
<wikitex>[[Файл:кирк2.png|right|420px|thumb|Последовательность триангуляций.]][[Файл:кирк3.png|right|420px|thumb|Структура триангуляций.]]Итак, имеется N-вершинная триангуляция $G$, и пусть строится последовательность триангуляций $S_1, S_2, \dots, S_{h(N)}$, где $S_1 = G$, а $S_i$ получается из $S_{i - 1}$ по следующим правилам:
* Шаг 1. Удалим некоторое количество неграничных и независимых (попарно несмежных друг с другом) вершин и инцидентные им ребра (от выбора этого множества напрямую зависит оптимальность алгоритма).
* Шаг 2. Построить триангуляцию получившихся в результате шага 1 многоугольников.
Очевидно, что треугольники из $S_1$ (и только они) не имеют исходящих ребер.
====Выбор множества удаляемых вершин====
Как уже упоминалось, от выбора множества вершит триангуляции, которые будут удалены при построении $S_i$ по $S_{i-1}$ существенно зависит эффективность метода. Предположим, что можно выбрать это множество так, чтобы выполнялись следующие ''свойства'' ($N_i$ обозначает число вершин в $S_i$):
