Section outline

  • News

    Fäll ihop allt Expandera allt

  • General

    Computational Geometry (german: Algorithmische Geometrie) is concerned with algorithmic questions where the input and/or ouput features geometric objects such as points, line-segments, lines, circles, polygons, planes, and polyhedrons; examples include the computation of triangulations, convex hulls, Voronoi Diagrams, or geometric shortest paths. Problems of this nature arise in many areas of computer science that involve storage, analysis, construction, and manipulation of spatial data; examples include robotics, geographic information systems, CAD/CAM, computer graphics, video games, and virtual reality. This course is concerned with techniques and concepts related to the design and analysis of algorithms and data structures for geometric problems. Every technique and concept will be illustrated by way of a concrete problem that arises in one of the mentioned application areas.

    At the end of this course, students should be able to devise efficient algorithmic solutions for basic geometric problems. To this end, they should learn (to apply) fundamental geometric algorithms and data structures, as well as design principles and tools for the analysis of geometric algorithms.

    Lectures: Tuesday, 14:05 - 15:35, room SE III, computer science building M2 (begin: October 15)
    Exercises: Friday, 14:15 - 15:45, room SE I, computer science building M2 (begin: October 25)
    Lecturers: Boris Klemz    (lectures), Tino Reith (exercises)
    Exam: Date/format to be announced.
    A bonus of 0.3 will be applied to the exam grade of students that pass the exam and score at least 50% of the total points achievable in the exercises. 
    Credits: 5 ECTS (2+2 SWS)

    Module: Algorithmische Geometrie (english: Computational Geometry)
    Prerequisites:    Strongly recommended: Algorithms and Data Structures (Bsc. Computer Science) or a comparable course. In particular, you should be familiar with basic algorithms (binary search, sorting, DFS/BFS, shortest path computation, ...), data structures (arrays, lists, stacks, queues, search trees, ...), algorithmic design principles (recursion, divide and conquer, dynamic programming, greedy algorithms, ...), analysis of algorithms (big O Notation, amortization, recurrence relations, master theorem, ...), basic graph theory and terminology, and basic mathematical concepts (proof techniques, basic combinatorics, ...). Ideally, you also attended some slightly more advanced algorithmic course, e.g., Algorithmic Graph Theory (Bsc. Computer Science) or a comparable course.
    Target audience: Master Computer Science, Master Mathematics, Master Computational Mathematics
     Registration: To take the exam, a registration in WueStudy is mandatory.
    To access the course material, a registration in WueCampus necessary.