Geometrické algoritmy

12. přednáška

Delaunayova triangulace - algoritmus

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).