[compgeom-announce] Block Course on Complexity of Geometric Problems

[Christian Knauer <christian.knauer@inf.fu-berlin.de>]

Block Course on

Complexity of Geometric Problems

within the
Research Training Group (Graduiertenkolleg)
Methods for Discrete Structures
----------------------------------------------------------

Institute for Computer Science, Free University of Berlin
Sept. 17-28, 2007

Instructors:
Helmut Alt and Christian Knauer, possibly guest speekers
<http://www.inf.fu-berlin.de/groups/ag-ti/index.html>

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
<http://www.inf.fu-berlin.de> 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 aksed to register via email with  
Christian Knauer
<knauer@inf.fu-berlin.de>.


-- 
You are currently subscribed to compgeom-announce.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/compgeom-announce