Kombinatoricka a vypocetni geometrie I 2015/2016
Combinatorial and Computational Geometry I 2015/2016
(Jan Kyncl, Martin Tancer, KAM)

Prednaska: v utery od 12:20 v S4. Prednaska je letos v anglictine, muzete se ale ptat i cesky.

Lecture: Tuesdays at 12:20 in S4. The lectures are in English this year, but you can also ask questions in Czech.

Seznam odprednesene latky najdete na konci teto stranky.

For the list of topics covered please see the end of this page.

Cviceni: po prednasce 14:00 v S4 podle rozvrhu na strance cviceni. Cviceni jsou cesky i anglicky.

Exercise sessions: after the lecture at 14:00 in S4 according to the schedule on the exercise webpage. The exercises are both in Czech and English.

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 probrane v lonske prednasce.

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 contents of Part II varies among the years, each year covering a few selected topics in more depth.

Osnova
Zakladni vety o konvexnich mnozinach (Radonova, Hellyho veta), Minkowskeho veta, geometricka dualita, incidence bodu a primek, definice a zakladni vlastnosti konvexnich mnohostenu, kombinatoricka slozitost konvexnich mnohostenu (cyklicke mnohosteny), Voroneho diagram a Delaunayova triangulace, arrangementy nadrovin (pocet sten, veta o zone), strategie "zametani roviny " (hledani pruseciku usecek), strategie "pravdepodobnostni inkrementalni konstrukce ", problem lokalizace bodu, vypocet konvexniho obalu, konstrukce arrangementu, linearni programovani v male dimenzi, triangulace mnohouhelnika v rovine.

Outline
Basic theorems on convex sets (Hellyho, Radon, Caratheodory, separation). Minkowski's theorem on lattice points in convex bodies. Geometric duality. Line-point incidences. Convex polytopes: definition, basic properties, maximum number of faces. Voronoi diagrams. Hyperplane arrangements. Introduction to algorithms of computational geometry. Randomized incremental algorithms.

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).
• 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).
• 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

Topics covered:

Lecture 6.10. (JK)

• Introductory information
• Basic notions: d-dimensional 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)
• Hyperplane separation theorem, almost full proof for the case of two compact sets, idea for the case of bounded sets
• Radon's theorem (so far only statement)

Lecture 13.10. (JK)

• Radon's theorem with proof
• Helly's theorem
• Infinite version of Helly's theorem
• Existence of a centerpoint
• Ham sandwich theorem (only statement)
• Center transversal theorem (only statement)
• Drawing of a graph, crossing number of a graph

Lecture 20.10. (JK)

• Easy upper and lower bounds on the crossing number of K_n
• Crossing lemma
• Szemeredi–Trotter theorem about incidences between points and lines
• Lower bound on the number of incidences between n points and n lines
• Upper bound O(n^{4/3}) on the number of unit distances (only statement)
• Lower bound n^{1+c/(log log n)} on the number of unit distances (description of the construction, no proof)

Lecture 27.10. (MT)

• Minkowski's Theorem on centrally symmetric convex sets
• Application: Can you see out of a regular forest?
• Lattices, the determinant of a lattice.
• Minkowski's Theorem for lattices.
• An application in number theory: each prime number of the form 4k + 1 can be written as a sum of two squares.

Lecture 3.11. (JK)

• Geometric duality: duality transform D_0 between points and hyperplanes avoiding the origin, dual set X*, duality transform D between points and nonvertical hyperplanes
• Convex polytopes: V-polytopes, H-polyhedron, H-polytope, dimension of a polytope
• Basic examples: d-dimensional cube, crosspolytope and simplex
• Every H-polytope is a V-polytope

Lecture 10.11. (JK)

• Every V-polytope is a H-polytope
• Face of a polytope P, facet, edge, vertex, every face is a convex polytope
• Extremal point of a set
• The extremal points of P are exactly its vertices, P is the convex hull of its vertices
• The vertices of a face F of P are exactly those vertices of P that lie in F
• The faces of a face F of P are exactly those faces of P that lie in F (sketch)
• Graph of a polytope, the graph of a 3-dimensional polytope is planar
• Steinitz's Theorem, Balinski's Theorem (only statement)

Lecture 24.11. (JK)

• Face lattice of a polytope and its properties, combinatorial equivalence of polytopes
• Dual polytope P*, the face lattice of a dual polytope is "upside down" and j-faces of P correspond to (d-1-j)-faces of P* (without proof)
• Simplicial polytope, simple polytope, examples
• The f-vector of a polytope, estimates on the number of faces of 3-dimensional polytopes, definition of neighborly polytopes
• Moment curve, cyclic polytope, Gale's evenness criterion characterizing facets of the cyclic polytope

Lecture 1.12. (JK, MT)

• Exact number of facets of the d-dimensional cyclic polytope with n vertices
• The upper bound theorem (only statement)
• An asymptotic version of the upper bound theorem (proof only for simplicial polytopes)
• Voronoi diagrams. Unit paraboloid, a polyhedron that projects to the Voronoi diagram.
• An upper bound on the number of faces of all regions of the Voronoi diagram (started).

Lecture 8.12. (MT)

• An upper bound on the number of faces of all regions of the Voronoi diagram (finished).
• Arrangements of hyperplanes in the d-space. Cells and k-faces of an arrangement.
• Simple arrangements of hyperplanes, counting the number of cells of a simple arrangement.
• An arrangement of general subsets of the d-space.
• Zero sets of polynomials and their arrangement(s). Number fo faces in such a case (started).

Lecture 15.12. (MT)

• Sign patterns of a collection of polynomials.
• Milnor-Thom theorem.
• (Affine) arrangements of pseudolines. Wiring diagram as one combinatorial description.
• An (affine) isomorphism of arrangements of pseudolines, stretchability.
• The most of the arrangements of pseudolines are not stretchable. (Milnor-Thom theorem inside!)
• Number of vertices in level at most k (started).

Lecture 22.12. (MT)

• Clarkson's theorem on levels. Proof only for d=2 and for simple arrangements.
• The zone theorem. Proof again only for simple arrangements. Easy proof for cells (i.e., d-faces).
• Otherwise, the proof of the zone theorem started for (d-1)-faces by induction in d. (Not finished yet.)

Lecture 5.1. (MT)

• Finishing the proof of the zone theorem (for (d-1)-faces).
• Geometric algorithms.
• Naive, O(n^2 log n), and incremental, O(n^2), algorithm for a construction of an arrengement of n lines.
• Incremental algorithm for the convex hull of n-points working in time O(n log n).
• Output-sensitive algorithm for the convex hull with running time O(n log h) where h is the number of points on the convex hull. (Some subroutines were not explained in detail.)

Lecture 12. 1. (MT)

• The point localization problem and determining a segment above a query point.
• The trapezoidal decomposition of a set of segments. A suitable data structure for it.
• Localization of a query point in this data structure takes expected O(log n) time.
• It takes expected O(n log n) time to build this structure and the expected storage is O(n).