Algoritmy pro Minkowského součet mnohoúhelníků

• Název práce v češtině: Algoritmy pro Minkowského součet mnohoúhelníků
• Název v anglickém jazyce: Algorithms for Minkowski sums of polygons
• Klíčová slova: Minkowského součet|Winding number|Nekonvexní mnohoúhelníky|Konvoluční metoda|Rozkladová metoda
• Klíčová slova anglicky: Minkowski sum|Winding number|Non-convex polygons|Convolution Method|Decomposition Method
• Akademický rok vypsání: 2022/2023
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: RNDr. Zuzana Patáková, Ph.D.
• Řešitel: Bc. Daniel Šimek - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.02.2023
• Datum zadání: 15.02.2023
• Datum potvrzení stud. oddělením: 21.02.2023
• Datum a čas obhajoby: 12.09.2023 10:00
• Datum odevzdání elektronické podoby: 18.07.2023
• Datum odevzdání tištěné podoby: 24.07.2023
• Datum proběhlé obhajoby: 12.09.2023
• Oponenti: doc. Mgr. Pavel Příhoda, Ph.D.

Zásady pro vypracování

Máme-li množiny A, B, pak jejich Minkowského součtem rozumíme množinu všech prvků tvaru a + b, kde a je z A a b je z B.

Cílem práce je popis a porovnání následujících algoritmů pro výpočet Minkowského součtu dvou nekonvexních mnohoúhelníků:
1) pomocí rozkladu na konvexní mnohoúhelníky
2) pomocí konvoluční metody

Student ilustruje své výsledky na příkladech. K tomu lze využít software CGAL, kde jsou obě výše zmíněné metody implementovány.

Seznam odborné literatury

P. K. Agarwal, E. Flato, D. Halperin: Polygon decomposition for efficient construction of Minkowski sums. Computational Geometry: Theory and Applications, 21:39–61, 2002.
E. Flato, D. Halperin: Robust and efficient construction of planar Minkowski sums. In Abstracts 16th European Workshop Comput. Geom., pages 85–88, 2000.
R. Wein: Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method. In ESA 2006.
L. Guibas, L. Ramshaw, J. Stolfi: A kinetic framework for computational geometry, In Proceedings of 24th Annual Symposium on Foundations of Computer Science, 1983.

Předběžná náplň práce

Minkowského součet je důležitý nástroj ve výpočetní geometrii a má všestranné aplikace. Zmiňme například robot motion planning (pohybující se objekt mezi překážkami) či design řízený počítačem.