Geometrické algoritmy
1. přednáška
Algoritmy pro konvexní obaly v rovině
Konvexní množina v rovině, konvexní obal množiny, konvexní obal množiny n bodů. Naivní algoritmus pro konvexní obal. Efektivní algoritmus (Graham Scan) pracující v čase O(n log n). Lexikografické uspořádání bodů, horní a dolní konvexní obal. Jak matematicky vyjádřit "zatáčku vpravo". Pseudokód. Okrajově další možné algoritmy.
Literatura pro celou přednášku
Xerox staršího vydání knihy je po jednotlivých kapitolách k dostání v Marečkově knihkupectví.