Advanced geometry (2015/2016)

Course code
4S003197
Name of lecturer
Giuseppe Mazzuoccolo
Coordinator
Giuseppe Mazzuoccolo
Number of ECTS credits allocated
6
Academic sector
MAT/03 - GEOMETRY
Language of instruction
English
Period
II semestre dal Mar 1, 2016 al Jun 10, 2016.

Lesson timetable

II semestre
Day Time Type Place Note
Monday 9:30 AM - 11:30 AM lesson Lecture Hall M  
Wednesday 1:30 PM - 3:30 PM lesson Lecture Hall M  

Learning outcomes

Introduction to Graph Theory, Discrete Geometry and Computational Geometry.

Syllabus

GRAPH THEORY
-Definitions and basic properties.
-Matching in bipartite graphs: Konig Theorem and Hall Theorem. Matching in general graphs: Tutte Theorem. Petersen Theorem.
-Connectivity: Menger's theorems.
-Planar Graphs: Euler's Formula, Kuratowski's Theorem.
-Colorings Maps: Four Colours Theorem, Five Colours Theorem, Brooks Theorem, Vizing Theorem.

DISCRETE GEOMETRY
-Convexity, convex sets convex combinations, separation. Radon's lemma. Helly's Theorem.
-Lattices, Minkowski's Theorem, General Lattices.
-Convex independent subsets, Erdos-Szekeres Theorem.
-Intersection patterns of Convex Sets, the fractional Helly Theorem, the colorful Caratheodory theorem.
-Embedding Finite Metric Space into Normed Spaces, the Johnson-Lindenstrauss Flattening Lemma
-Discrete surfaces and discrete curvatures.

COMPUTATIONAL GEOMETRY
-General overview: reporting vs counting, fixed-radius near neighbourhood problem.
-Convex-hull problem: Graham's scan and other algorithms.
-Polygons and Art Gallery problem. Art Gallery Theorem, polygon triangulation.
- Voronoi diagram and Fortune's algorithm.
- Delaunay triangulation properties and Minimum spanning tree.

Assessment methods and criteria

Written exam (120 minutes) and oral exam.

STUDENT MODULE EVALUATION - 2015/2016