5. přednáška
Triangulace monotónních mnohoúhelníků
Triangulace monotónních mnohoúhelníků metodou zametací přímky. Jednoduché nalezení další události, žádný binární strom. Místo toho stack - část monotónního mnohoúhelníka nad zametací přímkou, která dosud nebyla triangulována. Algoritmus pracuje v lineárním čase. Pseudokód na straně 13 souboru dole.
Průnik polorovin a úloha lineárního programování v rovině
Motivace: problém, jak najít vhodnou formu na odlévání odlitku ve tvaru mnohoúhelníka vede k úloze najít v rovině aspoň jeden bod v průniku n polorovin. Pro řešení této úlohy uvedeme dva algoritmy, které řeší trochu víc. Prvý popíše celý průnik polorovin, druhý hledá maximum lineární funkce na průniku polorovin.
Průnik n polorovin hledáme metodou rozděl a panuj. Ten vede na hledání průniku dvou mnohoúhelníkových konvexních oblastí. Pojem levé a pravé cesta. Metoda zametací přímky. Události jsou vrcholy, jejich pořadí díky konvexitě najdeme jednoduše. Probráním několika situací najdeme hrany v levé a pravé cestě průniku. Potřebný čas je O(n log n).
Úloha lineárního programování v rovině - formulace problému.
Pseudokódy algoritmů najdete na stranách 13 a 14 následujícího souboru