[ICGeo] - [2024Winter] - [en] - [Computational Geometry]


Computational Geometry [2024 SoSe]
Code
ICGeo
Name
Computational Geometry
CP
8
Duration
one semester
Offered
irregular
Format
Lecture 4 SWS + Exercise course 2 SWS
Workload
240 h; thereof
90 h lectures and tutorials
15 h preparation for exam
135 h self-study and working on assignments/projects (optionally in groups)
Availability
M.Sc. Angewandte Informatik
M.Sc. Data and Computer Science
M.Sc. Scientific Computing
Language
English
Lecturer(s)
Susanne Krömker
Examination scheme
Learning objectives The students know the algorithms and data structures of geometric and topological data processing.
They can understand and implement sweep algorithms for nearest neighbors, intersections of line segments and Voronoi diagrams, can construct alpha shapes and beta skeletons from pointclouds, know template-based and data-driven algorithms for the determination of isolines and isosurfaces, can work with discrete vector fields on simplicial complexes and know about persistence of topological invariants.
They master the associated data structures for efficient storage and further processing and can calculate the complexity of the various algorithms.
Learning content Basic concepts from geometry, graph theory and topology, sweep algorithms in visibility analysis and Voronoi diagrams, Delaunay triangulations, alpha shapes, beta skeletons, isosurfaces, discrete Morse theory
Requirements for participation recommended is: Algorithmen und Datenstrukturen (IAD)
Requirements for the assignment of credits and final grade The module is completed with a graded oral examination. The final grade of the module is determined by the grade of the examination. The requirements for the assignment of credits follows the regulations in section modalities for examinations.
Useful literature Rolf Klein: Algorithmische Geometrie, Springer Verlag, 2005
Herbert Edelsbrunner: Geometry and Topology of Mesh Generation, Cambridge University Press, 2001
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry - Algorithms and Applications, 3rd edition, Springer, 2008
current publications