Search for contacts, projects,
courses and publications

Geometric Algorithms

Description

This course is an introduction to computational geometry and its applications. It 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. Computational geometry is well related to diverse application domains, where geometric algorithms play a fundamental role, such as pattern recognition, image processing, computer graphics, robotics, geographic information systems (GIS), computer-aided design (CAD), information retrieval, computational science, and many others. The course covers general algorithmic techniques, such as plane sweep, divide and conquer, incremental construction, randomization, and approximation, through their application to basic geometric problems.

The course will not be offered in the academic year 2016/17

REFERENCES

  • Computational Geometry, Algorithms and Applications; M. de Berg, O. Cheong, M. van Kreveld, M. Overmars; Springer-Verlag, 3rd ed., 2008

  • Optional: Computational Geometry in CJ. O’ Rourke, 2nd ed., Cambridge, University Press

  • Computational Geometry lecture notes; David Mount; www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf

People

 

Papadopoulou E.

Course director

Additional information

Semester
Spring
Academic year
2016-2017
ECTS
6
Education
Master of Science in Computational Science, Elective course, Lecture, 1st year

Master of Science in Informatics, Core course, Lecture, 1st and 2nd year

PhD programme of the Faculty of Informatics, Elective course, Lecture, 1st and 2nd year (4 ECTS)