[ICGeo] - [de] - [Computational Geometry]


Computational Geometry [2022/23 WiSe]
Code
ICGeo
Name
Computational Geometry
LP
8
Dauer
one semester
Angebotsturnus
irregular
Format
Lecture 4 SWS + Exercise course 2 SWS
Arbeitsaufwand
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)
Verwendbarkeit
M.Sc. Angewandte Informatik
M.Sc. Data and Computer Science
M.Sc. Scientific Computing
Sprache
English
Lehrende
Susanne Krömker
Prüfungsschema
Lernziele 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.
Lerninhalte 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
Teilnahme-
voraus-
setzungen
recommended is: Algorithmen und Datenstrukturen (IAD)
Vergabe der LP und Modulendnote 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.
Nützliche Literatur 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