Triangulace mnohoúhelníků - rozdělení nekonvexního jednoduchého mnohoúhelníka na monotónní části

Art gallery problem: rozmístit v galerii tvaru nekonvexního mnohoúhelníka co nejmenší počet kamer, které mohou sledovat celou galerii. Matematická formulace: triangulace nekonvexního jednoduchého mnohoúhelníka a obarvení vrcholů třemi barvami tak, že v každém trojúhelníku jsou všechny barvy.

Algoritmus triangulace má dva kroky - rozdělení nekonvexního jednoduchého mnohoúhelníka na monotónní části a triangulaci monotónních částí. Definice monotónního mnohoúhelníka, typy vrcholů start, end, regular, split, merge. Mnohoúhelník je monotónní, právě když nemá vrcholy typu split a merge. Idea - pomocí diagonál směrem dolů likvidovat vrcholy typu split a pomocí diagonál nahoru likvidovat vrcholy typu merge.

Rozdělení na monotónní části. Sweep line algoritmus, události jsou vrcholy mnohoúhelníka. Vyvážený binární strom popisuje pořadí úseček protínajících zametací přímku a majících mnohoúhelník vpravo. Důležitý pojem "helper". Podle typu vrcholů -start, end, regular, split, merge - vedeme nové diagonály, měníme strom a helpery. Časová náročnost O(n log n), kde n je počet vrcholů.

Blackboards