Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Module INF-11-52-M-5

Computational Geometry (M, 4.0 LP)

Module Identification

Module Number Module Name CP (Effort)
INF-11-52-M-5 Computational Geometry 4.0 CP (120 h)

Basedata

CP, Effort 4.0 CP = 120 h
Position of the semester 1 Sem. in WiSe
Level [5] Master (Entry Level)
Language [DE/EN] German or English as required
Module Manager
Lecturers
Area of study [INF-VIS] Visualisation and Scientific Computing
Reference course of study [INF-88.79-SG] M.Sc. Computer Science
Livecycle-State [NORM] Active

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
2V+1U INF-11-52-K-5
Computational Geometry
P 42 h 78 h
U-Schein
ja PL1 4.0 WiSe
  • About [INF-11-52-K-5]: Title: "Computational Geometry"; Presence-Time: 42 h; Self-Study: 78 h
  • About [INF-11-52-K-5]: The study achievement [U-Schein] proof of successful participation in the exercise classes (ungraded) must be obtained. It is a prerequisite for the examination for PL1.

Examination achievement PL1

  • Form of examination: oral examination (15-30 Min.)
  • Examination Frequency: each semester
  • Examination number: 61152 ("Computational Geometry")

Evaluation of grades

The grade of the module examination is also the module grade.


Contents

Formal Foundations
  • Foundations of Computational Geometry
  • Relevant Operations on Spatial Data
  • Efficient Data Structures for Spatial Data
  • Algorithm Design Strategies:
    • sweep-line algorithms
    • randomized algorithms
    • output-sensitive algorithms
  • Runtime and memory analysis of complex geometric algorithms
  • Duality transforms and duals of an object

Sweep-Line Algorithms

  • Convex Hull
  • Line Segment Intersection
  • Polygon Triangulation
  • Voronoi Diagrams

Randomized Algorithms

  • BSP Tree Contstruction
  • Trapezoidal Maps
  • Delaunay Triangulation

Efficient spatial data structures and their applications

  • Quadtrees and Octrees
  • Binary-space-partition (BSP) Trees
  • kd-Trees and Range Trees
  • Trapezoidal Maps

Competencies / intended learning achievements

Successful completion of the module will enable students to
  • explain, implement, and analyze important algorithms of computational geometry,
  • select suitable algorithms for the solution of geometric problems
  • apply algorithmic design strategies of computational geometry to novel problems and analyze the resulting algorithms

Literature

  • J. O'Rouke: Computational Geometry in C, Cambridge University Press, 1998.
  • H. Edelsbrunner: Geometry and Topology of Mesh Generation, Cambridge University Press, 2001.
  • M. de Berg, M. van Kreveld: Computational Geometry — Algorithms and Applications, Springer, 2000.
  • current scientific literature.

Requirements for attendance (informal)

None

Requirements for attendance (formal)

None

References to Module / Module Number [INF-11-52-M-5]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science Specialization 1 [WP] Compulsory Elective
Module-Pool Name
[INF-VIS_Ba_V-MPOOL-4] Specialization Bachelor TA Visualization and Scientific Computing