Nicola Wolpert [an error occurred while processing this directive]

• Research
• Publications
• Teaching

---

Vertiefungsvorlesung Wintersemester 2004/2005:

Exakte und Effiziente Algorithmen für Kurven und Flächen

Dr. Lutz Kettner, Dr. Susanne Schmitt, Dr. Nicola Wolpert

	Leistungspunkte: 9
	Vorlesung: Dienstag und Donnerstag, 9.00 - 11.00,
	am MPI (Gebäude 46), Hörsaal 024
	Übung: Dienstag, 16.00 - 18.00,
	am MPI (Gebäude 46), Raum 021

Vorlesungsinhalt:

In dieser Vorlesung diskutieren wir Probleme, die bei der
Implementierung geometrischer Algorithmen auftreten.
Speziell wollen wir uns mit der Frage beschäftigen, wie
man bekannte Methoden aus der algorithmischen Geometrie,
die mit Linien und Liniensegmenten als Eingabe arbeiten,
auf Kurven und gekrümmte Flächen übertragen kann.
Ein Beispiel mit grosser praktischer Relevanz, z.B. bei der Fertigung
mechanischer Teile für den Automobilbau, ist die
Durchführung boolescher Operationen auf gekrümmten
Polygonen und Polyedern. Solche Operationen sind sehr anfällig
gegen Rundungsfehler. Wir wollen Datenstrukturen und Algorithmen
entwickeln, die die booleschen Operationen sowohl exakt als auch
effizient durchführen können.

Im Einzelnen werden wir uns in der Vorlesung mit folgenden Themen
beschäftigen:

	arithmetische Präzision, Separationsschranken
	Floating point Filter
	Rechnen mit algebraischen Zahlen
	Kurven und deren Arrangements
	quadratische Flächen und deren Arrangements
	Softwarestruktur in LEDA und CGAL
	C++ Techniken

Die Vorlesung vertieft die Inhalte des Proseminars "Theorie und
Praxis geometrischer Algorithmen" aus dem Sommersemster 2004. Zur
erfolgreichen Teilnahme an der Vorlesung sind die Vorkenntnisse aus
dem Proseminar hilfreich aber nicht erforderlich. Im Anschluss an
diese Veranstaltung bieten wir Bachelor-, Master-, und Diplomarbeiten
an. Beispiele und weitere Informationen kann man der Projektseite
EXACUS (Efficient and Exact Algorithms for Curves and Surfaces)
am MPII entnehmen.

Übungen:

Übung 1
Übung 2
Übung 3
Übung 4
Übung 5
Übung 6
Übung 7
Übung 8
Übung 9
Übung 10 und Maple-File
Übung 11
Übung 12
Übung 13
Übung 14

Begleitende Literatur:

LEDA-book, Section 10.7, Line Segment Intersection
Stefan Schirra, A Case Study on the Cost of Geometric Computing
LEDA-book, Chapter 9, Geometry Kernels
Remark on floating point arithmetik
Rechnen mit garantierter Präzision
Proofs for algebraic numbers
ggt von Polynomen
Termination proof for Uspensky
The Jacobi-curve cuts transversally through intersections of multiplicity 2: Proof
References for Nef-Polyhedra