Nicola Wolpert [an error occurred while processing this directive]

• Research
• Publications
• Teaching

---

Lecture Wintersemester 2003/2004:

Effective Computational Geometry for Curves and Surfaces

by 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.

Exercises:

Exercise 1
Exercise 2
Exercise 3
Exercise 4
Exercise 5
Exercise 6

Course Notes:

LEDAbook Section 10.7, Line Segment Intersection
Raimund Seidel, Backwards Analysis of Randomized Geometric Algorithms
Stefan Schirra, A Case Study on the Cost of Geometric Computing
LEDAbook Chapter 9, Geometry Kernels
Proofs for algebraic numbers
Remark on floating point arithmetik
LEDA reals
separation bound for real algebraic expressions
(there is a mistake in the paper: u(E) is wrong for the diamond operator,
the version in the lecture was correct)
diamond operator
Termination proof for Uspensky
Proof for Sturm sequences
E. Berberich et al., A computational basis for conic arcs and boolean operations on conic polygons
Jacobi curves
References for Nef-Polyhedra