Kombinatorická a výpočetní geometrie II (2019/2020)

Combinatorial and Computational Geometry II (2019/2020)

Jan Kynčl, Pavel Valtr, KAM

Záznam v SISu
Entry in SIS

Přednáška: úterý 15:40 v S1 (začínáme 25.2.)

Lecture: Tuesdays 15:40 in S1 (we start on 25.2.)

Cvičení: konají se v úterý 17:20 v S1 (po přednášce) podle rozvrhu na stránce cvičení. První cvičení je v plánu 25.2.

Exercise sessions: after the lecture at 17:20 v S1 according to the schedule on the exercise webpage. The first exercise is planned on 25.2.

Anotace:
Navazuje na přednášku Kombinatorická a výpočetní geometrie I. Letošní předběžný plán: konvexně nezávislé množiny, půlící přímky, složitost dolní obálky úseček a Davenport–Schinzelovy posloupnosti, zlomková Hellyho věta, barevná Carathéodoryho věta, Tverbergova věta, další témata.

Annotation:
A continuation of the lecture Combinatorial and Computational Geometry I. A preliminary plan: convexly independent subsets, halving lines, complexity of the lower envelope of segments and Davenport–Schinzel sequences, fractional Helly theorem, colorful Caratheodory theorem, Tverberg theorem, other topics.

Literatura:
(bude průbežně doplňována)

[M] Hlavní zdroj: kniha J. Matoušek: Lectures on Discrete Geometry

Literature:
(will be updated during the semester)

[M] Main resource: the book J. Matoušek: Lectures on Discrete Geometry

Obsah přednášek:

25.2. (JK)

Konvexně nezávislé podmnožiny v rovině

3.3. (JK)

Konvexní díry v rovině Půlící přímky

10.3. (JK)

17.3. (samostatné studium)

[Ni] nebo [GGT] 6.2

24.3. (samostatné studium)

Dolní obálky a Davenport–Schinzelovy posloupnosti

[M] 7.1, 7.3, [N] 1.4, [P] 1.2, 1.3

31.3. (samostatné studium)

[M] 7.2

7.4. (samostatné studium)

[M] 7.4

14.4. (samostatné studium)

Průnikové vlastnosti konvexních množin

[M] 8.1, 8.2

21.4. (samostatné studium)

[M] 8.3

28.4. (samostatné studium)

Geometrické selekční věty

[M] 9.1, 9.2

5.5. (samostatné studium)

[M] 9.2

12.5. (samostatné studium)

[M] 9.3

19.5. (samostatné studium pro zájemce)

[S], [HNPT] Theorem 2.4 + Proof of Theorem 1.3




Topics of lectures:

25.2. (JK)

Convexly independent subsets in the plane

3.3. (JK)

Convex holes in the plane Halving lines

10.3. (JK)

17.3. (self-study)

[Ni] or [GGT] 6.2

24.3. (self-study)

Lower envelopes and Davenport–Schinzel sequences

[M] 7.1, 7.3, [N] 1.4, [P] 1.2, 1.3

31.3. (self-study)

[M] 7.2

7.4. (self-study)

[M] 7.4

14.4. (self-study)

Intersection patterns of convex sets

[M] 8.1, 8.2

21.4. (self-study)

[M] 8.3

28.4. (self-study)

Geometric selection theorems

[M] 9.1, 9.2

5.5. (self-study)

[M] 9.2

12.5. (self-study)

[M] 9.3

19.5. (optional self-study)

[S], [HNPT] Theorem 2.4 + Proof of Theorem 1.3