Combinatorial and Computational Geometry I

Combinatorial and Computational Geometry I 2019/2020

Kombinatoricka a vypocetni geometrie I 2019/2020

Lecture: Fridays at 9:00 in S9.
Prednaska: v patek od 9:00 v S9.

Exercise sessions: after the lecture at 10:40 in S9 according to the schedule on the exercise webpage.
Cviceni: po prednasce 10:40 v S9 podle rozvrhu na strance cviceni.

Extent of teaching: WINTER semester 2/2 (Exam and Exercise credit). Entry in SIS, syllabus
Rozsah vyuky: ZIMNI semestr 2/2 Z, Zk. Záznam v SISu, sylabus

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.

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.

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

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

Topics covered:

4.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, sketch of proof for the case of two compact sets, idea for the case of bounded sets

11.10. (JK)

Radon's theorem
Helly's theorem
Infinite version of Helly's theorem
Existence of a centerpoint
The ham sandwich theorem (only statement)

18.10. (JK)

Center transversal theorem (only statement)
Drawing of a graph, crossing number of a graph
Crossing lemma
Szemeredi–Trotter theorem about maximum number of incidences between points and lines

25.10. (JK)

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)
Minkowski's theorem for the integer lattice
Application 1: looking out of a regular forest
Application 2: Diophantine approximation of real numbers
Lattice with basis z_1, z_2, ..., z_d, the determinant of a lattice
Minkowski's theorem for general lattices (only statement)

1.11. (JK)

An application of the general Minkowski's theorem in number theory: each prime number of the form 4k + 1 can be written as a sum of two squares.
Geometric duality: duality transform D_0 between points (except 0) and hyperplanes avoiding the origin, dual set X*, duality transform D between points and nonvertical hyperplanes
Convex polytopes: V-polytope, H-polyhedron, H-polytope, dimension of a polytope
Basic examples: d-dimensional cube, crosspolytope and simplex
Every V-polytope is a H-polytope (sketch of a proof using duality and reverse implication)

8.11. (MT)

Every H-polytope is a V-polytope
Face of a polytope P, facet, edge, vertex
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
Graph of a polytope, the graph of a 3-dimensional polytope is planar
Balinski's theorem (only statement)
Steinitz's theorem (only statement)
Face lattice of a polytope, meets and joins, combinatorial equivalence of polytopes

15.11. (MT)

Further properties of the Face lattice of a polytope: graded, atomic and coatomic (sketched only)
Remark on efficient representation of the face lattice in a computer
Face lattice of the dual polytope is the inverse of the face lattice of the primal polyotp. In particular, j-faces of P correspond to (d-1-j)-faces of P*.
Simplicial and simple polytope, examples, the terms are mutually dual
f-vector of a polytope, bounds on the number of faces of a 3-polytope
Moment curve, cyclic polytope, intersection of the moment curve with a hyperplane, Gale criterion describing facets of the cyclic polytope
Number of faces of a polytope. Remark on Dehn-Sommerville equalities (without proof)

22.11. (MT)

Exact number of facets of the cyclic d-polytope with n vertices
Upper bound theorem (withou proof)
Asymptotic upper bound theorem (with proof), simplicialni polytopes first, then all.
Region of a point and Voronoi diagram.
Examples of applications of Voronoi diagrams: closest post office, interpolation of functions.
Unit paraboloid and a lemma on its tangent hyperplanes.

29.11. (MT)

Upper bound on complexity of a Voronoi diagram (via projection from certain polyhedron)
Arrangements of hyperplanes in R^d, number of vertices and cells in a simple arrangement of hyperplanes
Arrangements of more general geometric objects including zero sets of polynomials. Sign patterns of a set of polynomials.

6.12. (MT)

Milnor–Thom theorem (no proof)
Arrangement of pseudolines, wiring diagram, representation via permutations, equivalent arrangements
Stretchability of pseudoline arrangements, example of non-stretchable arrangement (non-simple one)
Asymptotic number (lower bound) of pseudoline arrangements, assymptotic number (upper bound) of line arrangements via Milnor-Thom. Consequence: there are many non-stretchable arrangements
Level of a vertex in a simple arrangement of hyperplanes.
Clarkson's theorem on level sets.
Sketch that this is tight. Proof in dimension 2 only via probabilistic technique.

13.12. (MT)

The zone theorem, proof for simple arrangements in dimension 2.
In general dimension: only counting the number of facets and (d-1)-faces (for simple arrangements).

20.12. (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

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

Temata prednasek: