Geometrické algoritmy
11. přednáška
Diagramy Voronoia
Demonstrace algoritmu.Časová a paměťová náročnost.
Delaunayova triangulace
Každá triangulace konvexního obalu daných n bodů v rovině má stejný počet trojúhelníků. Uspořádání triangulací lexikograficky pomocí velikosti úhlů. Pojmy: úhlově optimální triangulace, legální tringulace a Delaunayova triangulace. Platí: Triangulace je legální, právě když je Delaunayova.