Search for contacts, projects,
courses and publications

Geometric Algorithms

Description

COURSE OBJECTIVES

This course is an introduction to computational geometry and its applications. Computational geometry is well related to many application domains, such as pattern recognition, image processing, computer graphics, robotics, geographic information systems (GIS), computer-aided design (CAD), information retrieval, computational science, and others. The students will learn fundamental algorithmic techniques and practice in designing algorithms of their own.

 

COURSE DESCRIPTION

The course covers techniques needed in designing and analyzing efficient algorithms for computational problems in discrete geometry such as convex hulls, triangulations, geometric intersections, Voronoi diagrams, Delaunay triangulations, arrangements of lines and hyperplanes, and range searching. The course covers general algorithmic techniques, such as plane sweep, divide and conquer, incremental construction, randomisation, and approximation, through their application to fundamental geometric problems.

 

LEARNING METHODS

Lectures, exercise labs, homework sets on algorithmic problem solving

 

EXAMINATION INFORMATION
The course grade is determined by the results of homework assignments, an optional project, a midterm exam, and a final exam.

 

REFERENCES

  • Computational Geometry, Algorithms and Applications, 3rd Edition
  • M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Springer-Verlag, 2008
  • Lecture Notes of David Mount: http://www.cs.umd.edu/class/fall2016/cmsc754/Lects/cmsc754-fall16-lects.pdf

People

 

Papadopoulou E.

Course director

Additional information

Semester
Spring
Academic year
2020-2021
ECTS
6
Language
English
Education
Master of Science in Artificial Intelligence, Elective course, Lecture, 1st year
Master of Science in Artificial Intelligence, Elective course, Lecture, 2nd year
Master of Science in Computational Science, Elective course, Lecture, 1st year
Master of Science in Computational Science, Elective course, Lecture, 2nd year
Master of Science in Informatics, Elective course, Lecture, 1st year
Master of Science in Informatics, Elective course, Lecture, 2nd year
PhD programme of the Faculty of Informatics, Elective course, Lecture, 1st year (4 ECTS)
PhD programme of the Faculty of Informatics, Elective course, Lecture, 2nd year (4 ECTS)