Block Course
Block Course on
COMPLEXTITY OF GEOMETRIC PROBLEMS
within the
Research Training Group (Graduiertenkolleg)
Methods for Discrete Structures
Institute for Computer Science, Free University of Berlin
25.03.2008 - 04.04.2008
Instructors:
Helmut Alt and Christian Knauer,
possibly guest speakers
Format:
Lecture in the morning, 9 - 12
Problem solving in small groups in the afternoon
discussion of the solutions: 17-18
Topics:
- basics of computational geometry and complexity theory
- "easily solvable" geometric problems
- NP-hard geometric problems (e.g., packing and covering problems,
Euclidean shortest paths in 3 dimensions, minimum weight triangulation,
FrÈchet distance of surfaces)
- approximation algorithms, fixed parameter tractability, realistic inputs
- PSPACE-hard geometric problems (e.g., robot motion planning, linkage
reconfiguration)
- PSPACE - decidability of the 1st order theory of the reals with applications
- undecidable geometric problems
The language of the course is English.
Organizers: The course is offered by the Research Training Group
(Graduiertenkolleg) "Methods for Discrete Structures" of the Free
University, the Humboldt University and the Technical University in Berlin,
and is organized by Helmut Alt, Christian Knauer, and Tamara Knoll at the
Free University of Berlin.
Location: The course will be hosted by the Computer Science Department
of the Free University of Berlin.
Audience: This is a two week block course for graduate students (on the PhD
and the master level) working in Discrete Mathematics or in Computer
Science (in a broad sense). Participants are expected to have basic
knowledge in geometry, discrete mathematics, and algorithms and
complexity. The course is free of charge.
Registration: Participants are asked to register via email with Christian Knauer