Introduction to Combinatorial and Computational Geometry 2023/2024

Zaklady kombinatoricke a vypocetni geometrie 2023/2024

(Jan Kyncl, Pavel Valtr, KAM)

Lecture: Wednesday at 12:20 in S9. The lectures are in English this year, but you can also ask questions in Czech or Slovak.
Prednaska: Ve stredu od 12:20 v S9. Prednaska je letos v anglictine, muzete se ale ptat i cesky nebo slovensky.

Exercise sessions: after the lecture at 14:00 in S8 according to the schedule on the exercise webpage.
Cviceni: po prednasce 14:00 v S8 podle rozvrhu na strance cviceni.


Extent of teaching: WINTER semester 2/2 (Exam and Exercise credit). Entry in SIS, syllabus
Rozsah vyuky: ZIMNI semestr 2/2 Z, Zk. Stranka v SISu, sylabus

Annotation
Discrete geometry investigates combinatorial properties of geometric objects such as finite point sets or convex sets in Euclidean spaces. Computational geometry considers the design of efficient algorithms for computing with geometric configurations, and discrete geometry serves as its mathematical foundation. Part I of the course is a concise introduction. The lecture will be very similar to the last year. The contents of Part II varies among the years, each year covering a few selected topics in more depth.

Anotace
Vypocetni geometrie se zabyva navrhem efektivnich algoritmu pro geometricke problemy v rovine i ve vicedimenzionalnim prostoru (napr. je-li dano n bodu v rovine, jak co nejefektivneji najit dvojici bodu s nejmensi vzdalenosti). Takove problemy jsou motivovany aplikacemi v pocitacove grafice, prostorovem modelovani (napr. molekul, budov, soucastek), geografickych informacnich systemech a pod. Pri analyze takovych algoritmu se potrebuje kombinatoricka geometrie, studujici kombinatoricke vlastnosti geometrickych konfiguraci, konvexnich mnozin a pod. Vysledky jsou dulezite i z ciste matematickeho hlediska, napr. v teorii cisel. V teto uvodni prednasce se probiraji zakladni pojmy a metody, s durazem na matematicky zaklad (jine mozne podani by bylo z vice "informatickeho" hlediska, s durazem na datove struktury, implementaci algoritmu apod.). O naplni prednasky si muzete udelat lepsi predstavu podle latky probirane v minulych letech.

Literature

Literatura

Topics covered:

4.10.-8.11. (PV)

22.11. (JK)

29.11. (JK)

6.12. (JK)

13.12. (JK)

20.12. (JK)

3.1. (JK)

10.1. (JK)

Temata prednasek:

4.10.-8-11. (PV)

22.11. (JK)

29.11. (JK)

6.12. (JK)

13.12. (JK)

20.12. (JK)

3.1. (JK)

10.1. (JK)