FI:MA017 Geometric Algorithms - Course Information

MA017 Geometric Algorithms

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

• Applied Informatics (programme FI, N-AP)
• Information Technology Security (eng.) (programme FI, N-IN)
• Information Technology Security (programme FI, N-IN)
• Bioinformatics (programme FI, N-AP)
• Information Systems (programme FI, N-IN)
• Informatics (programme FI, B-INF) (2)
• Parallel and Distributed Systems (programme FI, N-IN)
• Computer Graphics (programme FI, N-IN)
• Computer Networks and Communication (programme FI, N-IN)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Embedded Systems (programme FI, N-IN)
• Service Science, Management and Engineering (eng.) (programme FI, N-AP)
• Service Science, Management and Engineering (programme FI, N-AP)
• Theoretical Informatics (programme FI, N-IN)
• Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
• Image Processing (programme FI, N-AP)

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.

• Enrolment Statistics (Autumn 2020, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2020/MA017