Kombinatorická a výpočetní geometrie 2 (2024/2025)
Combinatorial and Computational Geometry 2 (2024/2025)
Jan Kynčl, Martin Tancer, KAM
Stránka v SISu
Entry in SIS
Přednáška: středa 9:00 v S11
Lecture: Wednesdays 9:00 in S11
Cvičení: konají se ve středu v 15:40 v S10 podle rozvrhu na stránce cvičení.
Exercise sessions: Wednesdays 15:40 S10 according to the schedule on the exercise webpage.
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
- Konvexně nezávislé množiny:
- Půlící přímky:
- Dolní obálky a Davenport–Schinzelovy posloupnosti:
- Průnikové vlastnosti konvexních množin a geometrické selekční věty:
Literature:
(will be updated during the semester)
[M] Main resource: the book J. Matoušek: Lectures on Discrete Geometry
- Convexly independent subsets:
- Halving lines:
- Lower envelopes and Davenport–Schinzel sequences:
- Intersection patterns of convex sets and geometric selection theorems:
Obsah přednášek:
19.2. (JK)
Konvexně nezávislé podmnožiny v rovině
- Erdősova–Szekeresova věta, důkaz z Ramseyovy věty, důkaz dvojitou indukcí přes misky a čepice
26.2. (JK)
- Konstrukce množin bez k-misky a l-čepice
- Konstrukce množiny 2^{k-2} bodů bez k bodů v konvexní poloze
Konvexní díry v rovině
- k-díra, existence 5-díry, neexistence 7-díry v hortonovských množinách
Půlící přímky
- Půlící přímka, půlící úsečka
- Vždy existuje aspoň n/2 půlících přímek, pro body v konvexní poloze je to přesně n/2
- Definice h(n) = maximální možný počet půlících přímek pro n bodů v obecné poloze v rovině
5.3. (JK)
- Lovászův horní odhad h(n) <= O(n^{3/2})
- U každého bodu v úhlu proti dvěma sousedním půlícím úsečkám je přesně jedna další půlící úsečka
- Každá obecná přímka protíná nejvýše n/2 půlících úseček
- Dokončení odhadu h(n) <= O(n^{3/2}) pomocí rozkladu na pásy
- Geometrický graf půlících úseček splňuje následující identitu: součet počtu křížících se dvojic a kombinačních čísel ((d(v)+1)/2 nad 2) je roven (n/2 nad 2); důkaz spojitým přesouváním bodů z konvexní polohy
- Kombinací s průsečíkovým lemmatem dostaneme horní odhad h(n) <= O(n^{4/3})
- Konstrukce pro dolní odhad h(n) >= Omega(n log n)
- Nivaschův dolní odhad h(n) >= Omega((n/ln n) e^{(ln 4)^{1/2}(ln n)^{1/2}}):
- Dualita bodů a nesvislých přímek, bod p je nad přímkou l právě tehdy, když přímka D(p) je nad bodem D(l)
- Půlící přímky odpovídají vrcholům prostřední úrovně v duálním arrangementu
Topics of lectures:
19.2. (JK)
Convexly independent subsets in the plane
- Erdős–Szekeres theorem, proof from Ramsey's theorem, proof by double induction using cups and caps
26.2. (JK)
- Construction of point sets with no k-cup and no l-cap
- Construction of a set of 2^{k-2} points with no k points in convex position
Convex holes in the plane
- k-hole, existence of a 5-hole, nonexistence of a 7-hole in Horton sets
Halving lines
- Halving line, halving segment
- There are always at least n/2 halving lines, for n points in convex position exactly n/2
- Definition h(n) = maximum number of halving lines for n points in general position in the plane
5.3. (JK)
- Lovász's upper bound h(n) <= O(n^{3/2})
- Around each point in the wedge opposite to two consecutive halving segments there is exactly one halving segment
- Every generic line intersects at most n/2 halving segments
- Finishing the proof of the bound h(n) <= O(n^{3/2}) using a decomposition into parallel strips
- Geometric graph of halving segments satisfies the following identity: the sum of the number of crossing pairs and binomial coefficients ((d(v)+1)/2 choose 2) is equal to (n/2 choose 2); proof by continuous movement of points from convex position
- Combining with the crossing lemma we get the upper bound h(n) <= O(n^{4/3})
- Construction for the lower bound h(n) >= Omega(n log n)
- Nivasch's lower bound h(n) >= Omega((n/ln n) e^{(ln 4)^{1/2}(ln n)^{1/2}}):
- Duality of points and non-vertical lines, a point p is above a line l if and only if the line D(p) is above the point D(l)
- Halving lines correspond to vertices of middle level in the dual arrangement