Kombinatoricka a vypocetni geometrie I 2017/2018
Combinatorial and Computational Geometry I 2017/2018
(Jan Kyncl, Pavel Valtr, KAM)
Prednaska: v utery od 14:00 v S3.
Lecture: Tuesdays at 14:00 in S3.
Cviceni: po prednasce 15:40 v S3 podle rozvrhu na
strance cviceni.
Exercise sessions: after the lecture at 15:40 in S3 according to the schedule on the
exercise webpage.
Rozsah vyuky: ZIMNI semestr 2/2 Z, Zk. Záznam v SISu, sylabus
Extent of teaching: WINTER semester 2/2 (Exam and Exercise credit). Entry in SIS, syllabus
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.
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.
Literatura
-
Skripta Jiriho Matouska Introduction to Discrete Geometry
vysla v ITI Seriich (preprintova rada Institutu teoreticke informatiky MFF UK)
pod cislem 2003-150 a je k dispozici v informaticke knihovne MFF UK.
Tady jsou take jako
postscriptovy soubor, v nemz jsou pro usporu mista 2 male
stranky na jedne strance A4. Je urcen hlavne pro dvoustranny tisk
a ma vlevo okraj na svazani. A
zde PDF soubor
mysleny pro ctecky a tablety.
- Predchozi text je ve skutecnosti vyber casti obvykle probiranych
v prednasce z knihy J. Matousek: Lectures on Discrete Geometry.
- Text k casti o inkrementalnich geometrickych
algoritmech je k dispozici
zde
(12 str).
- Chanuv algoritmus pro konstrukci konvexniho obalu: doi:10.1007/BF02712873
- Kapitola "Geometricke algoritmy" ve skriptech Martina Marese
- Standardni uvodni text o vypocetni geometrii je
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational
Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997.
Informaticke oddeleni knihovny ma nekolik exemplaru.
-
J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press
1995
Literature
-
Jiri Matousek's lecture notes Introduction to Discrete Geometry, ITI Series 2003-150, available in the Computer Science library of MFF UK.
Here is a postscript file with two pages of text on one A4 page, intended for printing.
Here is a PDF file for readers and tablets.
- The lecture notes are, in fact, a selection of topics from the book J. Matousek: Lectures on Discrete Geometry.
- A text for the part about incremental geometric algorithms is available
here
(12 pages).
- Chan's algorithm for the construction of the convex hull: doi:10.1007/BF02712873
- A standard introductory text about computational geometry:
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational
Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997.
The computer science library of MFF UK has a few copies.
-
J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press
1995
Temata prednasek:
3.10. (JK)
- Uvodni informace
- Zakladni pojmy: d-rozmerny euklidovsky prostor R^d (mnozina usporadanych d-tic realnych cisel), nadrovina, uzavreny poloprostor
- Afinni podprostor, afinni obal, afinni kombinace, afinni (ne)zavislost
- Konvexni mnozina, konvexni obal, je roven mnozine vsech konvexnich kombinaci (naznak dukazu)
- Caratheodoryho veta (jen zneni, dukaz je jako cviceni)
- Veta o oddelovani nadrovinou, naznak dukazu, ze disjunktni kompaktni konvexni mnoziny lze ostre oddelit, myslenka pro pripad omezenych mnozin
10.10. (JK)
- Radonova veta
- Hellyho veta
- Nekonecna verze Hellyho vety
- Veta o centru
- Veta o sendvici (jen zneni)
- Center transversal theorem (jen zneni)
17.10. (JK)
- Nakresleni grafu, prusecikove cislo grafu
- Jednoduche odhady na prusecikove cislo K_n
- Prusecikove lemma
- Szemerediova–Trotterova veta o maximalnim poctu incidenci bodu a primek
24.10. (PV)
- Szemerediova–Trotterova veta o maximalnim poctu incidenci bodu a primek (dukaz pomoci prusecikoveho lemma)
- Dolni odhad pro m=n (popis konstrukce, vypocet bez nekterych podrobnosti)
- Horni odhad O(n^{4/3}) pro pocet jednotkovych vzdalenosti mezi n body v rovine (bez dukazu)
- zminka o konstrukci davajici dolni odhad n^{1+c/(log log n)} pro pocet jenotk. vzdalenosti
- Minkowskeho veta pro jednotkovou mrizku (zneni)
31.10. (PV)
- Minkowskeho veta pro jednotkovou mrizku (dukaz)
- aplikace Minkwskeho vety - lesik
- mrizka v d-dimenzionalnim prostoru, jeji determinant, Minkowskeho veta pro mrizku
7.11. (PV)
- aplikace Minkowskeho vety: aproximace realnych cisel
- geometricka dualita
- konvexni mnohosteny (H-mnohosteny, V-mnohosteny), vztah mezi temito pojmy
- kazdy V-mnohosten je H-mnohostenem
14.11. (PV)
- stena mnohostenu, vrchol, hrana, faseta
- priklady mnohostenu: simplex, d-dim. krychle (dulezitym prikladem je tez krizovy mnohosten
- byl v 2 prikladech na cviceni)
- simplicialni mnohosten, jednoduchy mnohosten,
dualni mnohosten
- svaz sten dualniho mnohostenu je "prevracenim" svazu sten puvodniho mnohostenu (bez
dukazu,
pouze intuitivni nahled rovinnymi obrazky)
- graf mnohostenu
- Steinitzova veta (bez dukazu)
- Veta o hornim odhadu (Upper Bound Theorem) - zneni
21.11. (PV)
- Veta o hornim odhadu (Upper Bound Theorem) - dukaz asymptoticke verze pro simplicialni
mnohosteny
(naznaceno, proc staci se na ne omezit)
- momentova krivka, cyklicky mnohosten, Galeovo kriterium, pocet faset cykl. mnohostenu
- Voroneho diagram pro mnozinu bodu v d-dim. prostoru
- Horni odhad slozitosti Vor. diagramu (dukaz pomoci svisle projekce jisteho H-mnohostenu v
(d+1)-dim. prostoru)
- Arrangementy nadrovin v R^d, pocet bunek arrangementu n nadrovin v R^d
- Veta o hladinach (zneni)
28.11. (PV)
- Veta o hladinach (dukaz)
- Veta o zone (dukaz v rovine a cast dukazu ve vice dimenzich)
5.12. (PV, JK)
- Veta o zone, dukaz pro jednoduche arrangementy ve vyssich dimenzich
- Druhy dukaz pro presny pocet bunek jednoducheho arrangementu n nadrovin v R^d
- Arrangement libovolnych podmnozin R^d
12.12. (JK)
- Arrangement nulovych mnozin polynomu, Milnorova–Thomova věta, asymptoticka a presnejsi verze (bez dukazu)
- Znamenkove kombinace mnoziny polynomu
- Arrangement pseudoprimek, wiring diagram, allowable sequence, izomorfni arrangementy
- Narovnatelnost arrangementu pseudoprimek, asymptoticky odhad poctu arrangementu pseudoprimek
19.12. (JK)
- Asymptoticky odhad poctu arrangementu primek (s vyuzitim Milnorovy–Thomovy vety), temer vsechny arrangementy pseudoprimek jsou nenarovnatelne
- Poznamky o algoritmicke slozitosti narovnatelnosti
- Pseudoarrangement bodu jako dual arrangementu pseudoprimek, order type, geometricka realizace pomoci celociselnych souradnic muze potrebovat exponencialni pocet bitu (bez dukazu)
- Power diagramy, jejich vlastnosti bez dukazu
- Kazdy H-polytop je i V-polytop
9.1. (JK)
- Inkrementalni algoritmus pro konstrukci arrangementu n primek v rovine v case O(n^2)
- Inkrementalni algoritmus na vypocet konvexniho obalu n bodu v rovine v case O(nlogn)
- Chanuv "output-sensitive" algoritmus na vypocet konvexniho obalu n bodu v rovine v case O(n log h), kde h je pocet vrcholu konvexniho obalu
Topics covered:
3.10. (JK)
- Introductory information
- Basic notions: d-dimensional Euclidean space R^d (the set of d-tuples of real numbers), hyperplane, closed halfspace
- Afinne subspace, afinne hull, afinne combination, afinne (in)dependence
- Convex set, convex hull, it is the set of all convex combinations (sketch of proof)
- Caratheodory's theorem (only statement, the proof is an exercise)
- Hyperplane separation theorem, almost full proof for the case of two compact sets, idea for the case of bounded sets
10.10. (JK)
- Radon's theorem
- Helly's theorem
- Infinite version of Helly's theorem
- Existence of a centerpoint
- The ham sandwich theorem (only statement)
- Center transversal theorem (only statement)
17.10. (JK)
- Drawing of a graph, crossing number of a graph
- Easy upper and lower bounds on the crossing number of K_n
- Crossing lemma
- Szemeredi–Trotter theorem about incidences between points and lines
...
5.12. (PV, JK)
- The zone theorem, proof for simple arrangements in higher dimensions
- Second proof for the exact number of cells of a simple arrangement of n hyperplanes in R^d
- Arrangement of arbitrary subsets of R^d
12.12. (JK)
- Arrangement of zero sets of polynomials, Milnor–Thom theorem, asymptotic and more precise version (no proof)
- Sign patterns of a collection of polynomials
- Arrangement of pseudolines, wiring diagram, allowable sequence, isomorphic arrangements
- Stretchability of pseudoline arrangements, asymptotic number of pseudoline arrangements
19.12. (JK)
- Asymptotic number of line arrangements (using the Milnor–Thom theorem), almost all pseudoline arrangements are nonstretchable
- Remarks about the algorithmic complexity of stretchability
- Pseudoarrangement of points as a dual of a pseudoline arrangement, order type, geometric realizations using integer coordinates may need exponentially many bits (without proof)
- Power diagrams, their properties without proofs
- Every H-polytope is a V-polytope
9.1. (JK)
- Algorithm for a construction of the arrangement of n lines in the plane: straightforward with running time O(n^2 log n), incremental with running time O(n^2)
- Incremental algorithm for the convex hull of n points in the plane with running time O(n log n)
- Chan's output-sensitive algorithm for the convex hull with running time O(n log h) where h is the number of vertices of the convex hull