Chciwa triangulacja

Chciwa triangulacja

Kroki triangulacji wielokąta Chciwego. Na każdym kroku dodawana jest nowa krawędź (czerwona) łącząca najbliższą parę wierzchołków, bez przekraczania poprzedniej krawędzi
Klasa	Algorytm wyszukiwania
Struktura danych	Kolejka priorytetowa Przestrzenna baza danych
Wydajność w najgorszym przypadku	${\ Displaystyle O (| V | \ cdot \ log | V |)}$
Najlepsza wydajność	${\ Displaystyle O (| V |)}$

Chciwa triangulacja to metoda obliczania triangulacji wieloboków lub triangulacji zbioru punktów przy użyciu schematu zachłanności , który dodaje krawędzie do rozwiązania jedna po drugiej w ściśle rosnącej kolejności według długości, z warunkiem, że krawędź nie może przeciąć wcześniej wstawionej krawędzi.