|
|
Computational Geometry
Wintersemester 2003/04
Lecturer:
Stefan Schirra
Lectures: (3 SWS)
Tuesday 7:30-9, G22A-217 (every other week)
Friday 9-11, G22A-218
| No lectures on |
Additional lectures on |
| Friday, November 27 |
|
Exercises: (1 SWS)
Tuesday 7:30-9, G22A-217 (every other week)
|
 |
Further information and course material
(for participants only -
username: firstname.lastname, password:
your matrikel number !)
Purpose:
The purpose of this course is to introduce students to the
design and analysis of efficient algorithms for combinatorial
geometric problems. Design techniques presented in the course
include
- incremental construction
- plane-sweep
- prune-and-search
- divide-and-conquer
- randomization
- duality and inversion
- parametric search
Topics covered include
- convex hull algorithms in 2D and 3D
- intersection of halfspaces
- triangulations
- Voronoi diagrams and Delaunay triangulations
Audience:
computer science (Hauptstudium and master),
computational visualistics (Hauptstudium and master)
Prerequisites:
Basic knowledge in algorithms and data
structures (such as sorting algorithms, balanced binary search trees,
lists, and stacks), and in the analysis of algorithms using
the Big-Oh notation.
Literature:
Textbooks and such on Computational Geometry
|
