Efektívne algoritmy a zložitosť - 05 - Minimálna triangulácia

Zhrnutie prednášky

Prednáška stručne zopakuje štyri kroky dynamického programovania: definíciu podproblémov a matice, rekurentný vzťah, bázové podproblémy a poradie vypĺňania. Potom zavedie problém minimálnej triangulácie konvexného mnohouholníka z oblasti výpočtovej geometrie, ktorá má aplikácie v počítačovej grafike a robotike. Vysvetlí pojmy konvexný mnohouholník, chorda a triangulácia (rozdelenie na neprekrývajúce sa trojuholníky nepretínajúcimi sa chordami). Cieľom je nájsť trianguláciu s najmenšou súčtovou dĺžkou použitých chord a obvodu. Podproblém T(U1…UL) je dĺžka najkratšej triangulácie mnohouholníka z vrcholov vybraných z pôvodného mnohouholníka v zachovanom poradí a prednáška začína odvodzovať rekurenciu.

• - Dynamické programovanie má štyri kroky: definícia podproblémov, rekurencia, bázové podproblémy a poradie vypĺňania matice.
• - Konvexný mnohouholník: spojnica ľubovoľných dvoch bodov na hranici leží vo vnútri.
• - Chorda je spojnica dvoch nesusediacich vrcholov mnohouholníka.
• - Triangulácia je rozdelenie mnohouholníka na neprekrývajúce sa trojuholníky pomocou nepretínajúcich sa chord.
• - Triangulácie zjednodušujú algoritmy v počítačovej grafike, ktoré pracujú s množinou trojuholníkov.
• - Hľadá sa triangulácia s minimálnou dĺžkou: súčet dĺžok chord plus obvod mnohouholníka.
• - Podproblém T(U1…UL) je minimálna triangulácia mnohouholníka z vrcholov vybraných z pôvodných v zachovanom poradí.

Zhrnutie pripravené s pomocou AI z prepisu videa.