Úvod do diskrétní a výpočetní geometrie

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Cílem předmětu je seznámit studenty s disciplínou diskrétní a výpočetní geometrie. Hlavním cílem kurzu je seznámit se s nejzákladnějšími objekty této disciplíny a umět řešit jednoduché algoritmické úlohy týkající se geometrie.

Požadavky:

Studenti by měli znát základní pojmy kombinatoriky, teorie grafů a analýzy algoritmů.

Osnova přednášek:

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.

Osnova cvičení:

bude doplněno

Cíle studia:

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.

Studijní materiály:

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.

Poznámka:

Předmět je vyučován v anglickém jazyce.

Další informace:

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

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: