Module Handbook

  • Dynamischer Default-Fachbereich geändert auf INF

Course INF-11-52-K-5

Computational Geometry (2V+1U, 4.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U) 4.0 CP 78 h
2 V Lecture 28 h
1 U Exercise class (in small groups) 14 h
(2V+1U) 4.0 CP 42 h 78 h

Basedata

SWS 2V+1U
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
Lecturers
Area of study [INF-VIS] Visualisation and Scientific Computing
Livecycle-State [NORM] Active

Possible Study achievement

  • Verification of study performance: proof of successful participation in the exercise classes (ungraded)
  • Details of the examination (type, duration, criteria) will be announced at the beginning of the course.

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

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)

Courses

Requirements for attendance (formal)

None

References to Course [INF-11-52-K-5]

Module Name Context
[INF-11-52-M-5] Computational Geometry P: Obligatory 2V+1U, 4.0 LP
Course-Pool Name
[INF-VIS_V-KPOOL-6] Lectures of the teaching area Visualization and Scientific Computing