Delaunayova triangulace - algoritmus

Náhodný přírustkový algoritmus, vše ve vhodném trojúhelníku p_-2, p_-1, p_0. 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).

Tabule z 12. přednášky

Tabule z 13. přednášky

Konvexní obal v R³    

Přírustkový náhodnostní algoritmus. Z konvexního obalu bodu r-1 bodů vytvoříme konvexní obal r bodů. Konfliktní seznamy, zachyceny v bipartitním grafu. Horizont viditelnosti je určen absencí dvojčat k viditelným  hranám.  Očekávaná paměťová a časová náročnost.

Tabule z 14. přednášky