Geometrické algoritmy
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.
Průnik 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í. Popis těchto oblastí pomocí levé a pravé hranice. Metoda zametací přímky. Události jsou vrcholy a v průběhu algoritmu spočítané průsečíky hranic. Hledáme vrcholy a hrany na levé a pravé hranici průniku. Potřebný čas je O(n log n).