MA017 Geometric Algorithms

Faculty of Informatics
Autumn 2020
Extent and Intensity
2/0/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
doc. John Denis Bourke, PhD (lecturer)
doc. RNDr. Martin Čadek, CSc. (lecturer)
Guaranteed by
doc. RNDr. Martin Čadek, CSc.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science
Timetable
Mon 16:00–17:50 A,01026
Prerequisites
Basic course on algorithms, high school geometry.
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 18 fields of study the course is directly associated with, display
Course objectives
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.
Learning outcomes
Students will gain knowledge about state-of-the-art algorithmic methods in this field, along with their complexity and underlying data and searching structures.
Syllabus
  • 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
Literature
    recommended literature
  • DE BERG, Mark, Otfried CHEONG, Marc VAN KREVELD and Mark OVERMARS. Computational geometry. 3rd ed. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-77973-5. URL info
Teaching methods
Lectures.
Assessment methods
Written exam. Requirements: to prove the knowledge of the theory from lectures and to be able to apply it to related problems.
Language of instruction
English
Further comments (probably available only in Czech)
Study Materials
The course is taught annually.
The course is also listed under the following terms Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2020, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2020/MA017