Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


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