Geometric Algorithms

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, geometric approximation. The course covers general algorithmic techniques, such as plane sweep, divide and conquer, incremental construction, randomization, and approximation, through their application to fundamental geometric problems.

This course is an introduction to computational geometry and its applications. Computational geometry is well related to a variety of 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 learn fundamental algorithmic techniques and practice in designing algorithms of their own.

• Istruzione di qualità

In presenza

Lectures, exercise labs, homework sets on algorithmic problem solving

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