MA017 Geometric Algorithms

Fakulta informatiky
podzim 2022
Rozsah
2/0/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
doc. John Denis Bourke, PhD (přednášející)
Garance
doc. RNDr. Martin Čadek, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Pá 10:00–11:50 A,01026
Předpoklady
Basic course on algorithms, high school geometry.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 18 mateřských oborů, zobrazit
Cíle předmětu
The aim of the course is to introduce the principles of basic algorithms in computational geometry. This course can be followed by the PA093 Computational Geometry Project where the students are implemented selected algorithms in practice.
Výstupy z učení
Students will gain knowledge about state-of-the-art algorithmic methods in this field, along with their complexity and underlying data and searching structures.
Osnova
  • 1. Algorithms for construction of convex hulls in two-dimensional space 2. Line segment intersections 3. Triangulations 4. Linear programming in two-dimensional space 5. Range searching (kd-trees, range trees) 6. Point localization 7. Voronoi diagrams 8. Duality and arrangements 9. Delaunay triangulation 10. Convex hulls in in three-dimensional space
Literatura
    povinná literatura
  • ČADEK, Martin. Geometrické algoritmy, Multimediální elektronický výukový materiál. 2018. URL info
    doporučená literatura
  • DE BERG, Mark, Otfried CHEONG, Marc VAN KREVELD a Mark OVERMARS. Computational geometry. 3rd ed. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-77973-5. URL info
Výukové metody
Lectures.
Metody hodnocení
Written exam. Requirements: to prove the knowledge of the theory from lectures and to be able to apply it to related problems.
Vyučovací jazyk
Angličtina
Informace učitele
https://is.muni.cz/auth/do/sci/UMS/el/geometricke-alg/index.html
A text for the course both in English and Czech can be find on the URL above.
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2023, podzim 2024.