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. (assistant)
prof. Ing. Jiří Sochor, CSc. (assistant)

Guaranteed by

prof. RNDr. Jan Slovák, DrSc.
Faculty of Informatics
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science

Timetable

Thu 16:00–17:50 A,01026

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)
• 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. Students will gain knowledge about state-of-the-art algorithmic methods in this field, along with their complexity and underlying data and searching structures. This course can be followed by the PA093 Computational Geometry Project where the students are implemented selected algorithms in practice.

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

• DE BERG, M., M. VAN KREVELD, M. OVERMARS and O. SCHWARZKOPF. Computational Geometry. 1st ed. Berlin: Springer-Verlag, 1997, 365 pp. ISBN 3-540-61270-X. 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 2018, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2018/MA017