Жадная триангуляция

Жадная триангуляция

Шаги триангуляции Polygon Greedy. На каждом шаге добавляется новое ребро (красное), соединяющее ближайшую пару вершин, не пересекая предыдущее ребро
Сорт	Алгоритм поиска
Структура данных	Приоритетная очередь Пространственная база данных
Худший вариант производительности	${\displaystyle O(|V|\cdot \log |V|)}$
Лучшая производительность	${\displaystyle O(|V|)}$

Жадная триангуляция — это метод вычисления полигональной триангуляции или триангуляции набора точек с использованием жадной схемы , которая добавляет ребра одно за другим к решению в строгом порядке возрастания длины, с условием, что ребро не может пересекать ранее вставленное ребро. ^{[1] [2]}