# Nonlinear Computational Geometry

Winter 08/09

The lecture gives an introduction to nonlinear computational geometry. Concepts from classical (linear) computational geometry (as convex sets, Voronoi diagrams, arrangements, trapezoidal decomposition,...) are introduced and applied to nonlinear objects. We aim for the design of algorithms that follow the exact computation paradigm, that is, their output reflects the exact mathematical result in any case. In order to do so we have to study methods to handle algebraic objects (points, curves, surfaces) in an exact manner. These methods comprise the representation of algebraic numbers, real root isolation as well as resultant computations. One of the goals will be the study of algorithms to determine the topology of algebraic plane curves and algebraic surfaces (see the AlcixWebdemo for a demonstration).
We are also planning to devote some time on possible applications such as robot motion planning.
### Prerequisites

Math for Computer Scientists I+II (or Analysis I+II and Linear Algebra I+II), basic knowledge in algorithms and data structures.
### Further Information

First Lecture: Friday 10-12 c.t. in room HS 001, Building E1 3, October 24th

Lectures: **Time/Room changed: Wednesday 14-16 c.t. in room 024, Building E1 4 **

Tutorials: Dates for the tutorials will be fixed in the first lecture.

Language: English or German (dependent on the audience)

#### Lecturers

- Dr. Michael Sagraloff, Building E1 4, R.306,Homepage
- Dr. Michael Hemmer, Building E1 4, R.329,Homepage

#### Grading

To get a graded certificate(6 CP) we expect the students to regularly attend
the lectures and tutorial sessions. In order to participate in the final exam,
one should reach about 50% of the possible points in the submited solutions for the
handed-out exercise sheets. The grade is determined by the final exam at the end of the
semester.
#### References

S. Basu, R. Pollack, and M.-F. Roy:
** Algorithms in Real and Algebraic Geometry**.
Springer, 2nd edition, 2006. An electronic version is available.

de Berg, van Kreveld, Overmars, and Schwazkopf:
**Computational Geometry**.
Springer, 2nd edition, 2000
E. Berberich, M. Kerber, M. Sagraloff:
**Exact Geometric-Topological Analysis of Algebraic Surfaces**.
SoCG 2008, pp. 164-173
(pdf, ps)

© ACM, 2008.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.

A. Eigenwillig, M. Kerber: **Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves**. SODA 2008, pp. 122-131 (pdf, ps).

© SIAM 2008. The provided download is an author-prepared version of the article.

A. Eigenwillig, M. Kerber, N. Wolpert: **Fast and Exact Geometric Analysis of Real Algebraic Plane Curves**. ISSAC 2007, pp. 151-158 (pdf, ps).

© ACM, 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use.

A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, and
N. Wolpert. **An Exact Descartes Algorithm with Approximate
Coefficients (Extended
Abstract)**. In *CASC*, volume 3718 of *LNCS*, pages 138-149, 2005.

Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner,
Kurt Mehlhorn, Joachim Reichel, Susanne Schmitt, Elmar Schömer, and Nicola Wolpert:
** EXACUS: Efficient and exact algorithms for curves and surfaces **.
ESA 2005, Springer, Oct. 2005. © Springer-Verlag.
(pdf,
ps)

E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, and E. Schömer:
** A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons **.
ESA 2002, Springer, Sept. 2002, pp. 174-186. © Springer-Verlag.
### Exercises

- Exercises will be supervised by Michael Kerber, Building E1 4, R.327,Homepage