Minimální triangulace mnohoúhelníku (Úlohy z MO kategorie P, 50. část) - Töpfer, Pavel (Matematika–Fyzika–Informatika, 2025)
Dnešním jubilejním 50. dílem uzavíráme dlouhodobý seriál článků, ve kterém jsme vás postupně seznámili s vybranými soutěžními úlohami z Matematické olympiády kategorie P (programování). Zmíněných 50 článků vycházelo na stránkách našeho časopisu od roku 2000 až do současnosti, tedy po dobu plných 25 let. Tentokrát si ukážeme jednu klasickou kombinatorickou úlohu, která byla zadána v celostátním kole 39. ročníku MO kategorie P ve školním roce 1989/90. Zabývá se tzv. triangulací mnohoúhelníku, což znamená rozdělení jeho plochy na samé trojúhelníky pomocí úhlopříček, které se vzájemně nikde nekříží. Jak uvidíme, efektivní řešení této úlohy bude založeno na myšlence dynamického programování, což je metoda velmi často využívaná nejen v různých soutěžních úlohách, ale i v programování obecně.