Selected Topics in Computational Geometry and Topology 1000-2M21GOT
i. Convex sets: Radon’s lemma, Helly’s and Tverberg’s theorems (2 lectures).
ii. Voronoi diagrams, Delaunay triangulations and Convex Hulls (1 lecture).
iii. The Clarkson-Shor method, Randomized Incremental Construction,
Backward Analysis (2 lectures).
iv. Range spaces, VC dimension, ε-nets and related structures, (2 lectures).
v. LP rounding (Bronnimann-Goodrich), Range search and point location algorithms. (1 lecture).
vi. Discrepancy theory (2 lectures).
vii. Metric embeddings and spanners (1 lecture).
viii. Graphs, Surfaces and Simplicial Complexes (1 lecture).
ix. Homology, Persistent Homology and Co-homology (2 lectures).
x. Morse Theory (1 lecture).
Main fields of studies for MISMaP
mathematics
Type of course
Mode
Prerequisites (description)
Course coordinators
Learning outcomes
Knowledge:
Knowledge of basic and some advanced techniques in computational geometry and topology.
A reasonably wide exposure to classic and modern problems.
Understanding the importance of mathematical proofs.
Skills:
Ability to apply geometric and topological concepts to algorithmic problems.
Ability to select appropriate tools from Discrete Geometry, or to tweak existing tools if required, to solve algorithmic or combinatorial problems in Geometry.
Competence:
Awareness of own limitations and the need for further study.
Development of the ability to read scientific articles, if necessary in a foreign language, to expand their knowledge.
Ability to precisely formulate questions to deepen their own understanding or to find gaps in reasoning.
Assessment criteria
2 homeworks and final paper presentation (approximately 25+25+50 percent).
Bibliography
J. Matoušek - Lectures on Discrete Geometry.
J. Matoušek - Geometric Discrepancy.
J-D. Boissonnat and M. Yvinec - Algorithmic Geometry.
Edelsbrunner and Harer - Computational Topology: An Introduction.
Selected recent papers.
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
- Bachelor's degree, first cycle programme, Computer Science
- Master's degree, second cycle programme, Computer Science
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: