Geometrické algoritmy
12. a 13. přednáška
Delaunayova triangulace
Pojmy: úhlově optimální triangulace, legální triangulace, Delaunayův graf a Delaunayova triangulace.Náhodný přírustkový algoritmus, vše ve vhodném trojúhelníku p-2, p-1, p0. Vyhledávací struktura D - acyklický orientovaný graf.Algoritmy DELAUNAYOVA TRIANGULACE a LEGALIZUJ HRANU. Změny ve vyhledávací strukture. Volba bodů počátečního trojúhelníka. Očekávaný čas konstrukce je O(n log n), ocekavané požadavky na paměť O(n).