Introduction to Discrete and Computational Geometry

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Theoretical Computer Science

Synopsis:

The aim of the course is to introduce students to the key principles of discrete and computational geometry, which plays an important role in computer science, robotics, computer graphics and geographic information systems. The course focuses on understanding basic geometric objects, algorithms and their applications in the field of computational geometry.

Fundamental concepts and used structures are gradually introduced in lectures. Students will become familiar with the theoretical foundations and effective algorithms for solving problems in these areas. Exercises are focused on practical applications of the discussed concepts, implementation of algorithms and solving computationally demanding problems.

Requirements:

The students are expected to be familiar with the basic notions of combinatorics, graph theory and analysis of algorithms.

Syllabus of lectures:

1. Introduction to Discrete and Computational Geometry

2. Introduction to Discrete and Computational Geometry

3. Convexity: Definition. Separation theorem. Convex hull in two dimensions: Definition and characterization.

4. Convex hull in two dimensions: Incremental algorithms. Divide-and-conquer algorithms. Graham algorithm. Lower bound.

5. Intersection of polygons: Basic notions about intersections of segments. Applications to intersection of polygons.

6. Triangulation of polygons and point sets: Existence. Art-gallery theorem. Algorithms. Trapezoidal decomposition. Triangulation of point sets.

7. Voronoi diagram: Definition. Applications. Properties. Divide-and-conquer algorithms. 

8. Delaunay triangulation: Definition. Applications. Properties. Other proximity graphs.

9. Arrangements of lines: Definition. Properties. Zone theorem. Algorithms. The DCEL.

10. Duality transforms: Definition. Properties. Sample problems.

11. (2) Linear programming in two dimensions: Definition. Prune-and-search algorithm. Randomized algorithm.

12. Point location: Definition. Kirkpatricks method. Applications.

Syllabus of tutorials:

Study Objective:

The main goal of the course is to learn the most fundamental tools used in geometric algorithms.

Study materials:

1. J. E. Goodman, J. ORourke, C. D. Tóth: Handbook on Discrete and Computational Geometry, 3rd edition. CRC Press, 2017. ISBN 978-1498711395.

2. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry: Algorithms and Applications, 3rd edition. Springer, 2008. ISBN 978-3-540-77974-2.

Note:

Further information:

https://courses.fit.cvut.cz/NI-DVG

No time-table has been prepared for this course

The course is a part of the following study plans: