Lecture Wintersemester 2003/2004:
Effective Computational Geometry for Curves and Surfaces

Instructors: Dr. Lutz Kettner, Dr. Susanne Schmitt, and Dr. Nicola Wolpert


Creditpoints: 9
Class: Tuesday and Thursday, 11.00 - 13.00,
at the MPI (Building 46), Room 024
Exercises: Wednesday, 16.00 - 18.00,
at the Mathematics Department (Building 27.2), Room ZS (Zeichensaal)

Course Topics:

In the lecture we address common problems in the implementation of algorithms in computational geometry, in particular, new questions when known methods for segments and lines are extended to curves and surfaces. We start with the traditional sweep-line algorithm and randomized- incremental construction. We discuss

arithmetic precision, separation bounds
floating point filters,
computation with algebraic numbers,
curves and curve arrangements,
quadric surfaces and surface arrangements,
software structure of LEDA and CGAL,
C++ techniques.

Our final goal is the development of data structures and of efficient and exact algorithms for boolean operations on curved polygons and curved polyhedra. Examples can be seen in the ongoing project EXACUS (Efficient and Exact Algorithms for Curves and Surfaces) at the MPII. In the continuation of the course we offer Fopra's and Thesis on theses topics.


Course Notes:

Lutz Kettner (<surname>@mpi-inf.mpg.de). Last modified on Tuesday, 17-Jan-2006 17:53:31 MET.