Combinatorial and Computational Geometry 2 (2022/2023)

Martin Tancer a Pavel Valtr

Záznam v SISu

Lecture: Friday 9:00 in S11

Exercise sessions: after the lecture at 10:40 v S5 according to the schedule on the exercise webpage.

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 (possibly shelling polytopes and the upper bound theorem).

(will be updated during the semester)

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

Topics of lectures:

17.2.,24.2.,3.3. (PV)

Convexly independent subsets in the plane Convex holes in the plane Halving lines

31. 3. (MT)

Intersection patterns of convex sets

[M] 8.1, 8.2, 8.3

14. 4. (MT)

[M] 8.3 (different proof of Tverberg's theorem) 9.1

Geometric selection theorems

21. 4. (MT)

[M] 9.2, 9.5, [Z] 8.1

Shellability of polytopes

28. 4. (MT)

[Z] 8.2, 8.3


5. 5. (MT)

[Z] 8.3, 8.4 (and a small bit of 0)

Upper bound theorem

12. 5. (MT)

[Z] 8.4