Anmeldung: bei S. Schmitt

Proseminar und Seminar zu ''Theorie und Praxis geometrischer Algorithmen'' - SS 2004

Prof. Dr. Kurt Mehlhorn, Dr. Susanne Schmitt, Dr. Nicola Wolpert

Ankündigung
Wie bestimmt man am schnellsten alle Schnittpunkte einer Menge von Liniensegmenten? Wie stellt man diese Schnittpunkte dar? Was passiert in Punkten, in denen sich mehr als zwei Geraden schneiden? Diese Fragen werden in den ersten beiden Vorträgen beantwortet. Das Ergebnis nennt man 'Arrangement von Liniensegmenten'.
Kann man auch Arrangements von Kurvensegmenten berechnen? Was ändert sich, wenn man statt Geraden Kurven betrachtet? Die Schnittpunkte können nicht mehr rational dargestellt werden, kann man sie trotzdem exakt berechnen? Es treten neue Probleme auf, kann man diese effizient lösen? Das werden wir in den weiteren Vorträgen des Proseminars lernen.
Unser Ziel ist die Entwicklung von Datenstrukturen und effizienten, exakten Algorithmen für boolsche Operationen auf Polygonen und Polyhedra, die durch Kurven beschrieben sind. Beispiele dafür findet man in dem Projekt EXACUS , das am MPII entwickelt wird.
Im Anschluss an das Proseminar werden Fopra's und Bachelor Arbeiten zu diesem Thema angeboten.

Betreuerinnen

Dr. Susanne Schmitt		Geb. 46 (MPII), Raum 318
Dr. Nicola Wolpert		Geb. 46 (MPII), Raum 323

Termine

Seminartermine:

Do 14-16 Geb. 46 (MPII), Raum 021

Themen

Datum	Thema	Vortragende/r	Betreuer/in	Literatur
22.4.	Line sweep (Seminarvortrag)	Roman Adam	Nicola	LEDAbook 10.7 Line segment intersection
29.4.	Algebraische Kurven	Holger Grzeschik	Nicola	C.G. Gibson: Elementary Geometry of Algebraic Curves, 1-2 Cox, Little, O'Shea: Ideals, Varieties, and Algorithms, S.134-137
6.5.	Isolierende Intervalle: Methode von Uspensky	Michael Arnold	Nicola	Fabrice Rouillier, Paul Zimmermann: Efficient isolation of polynomial real roots Collins, Loos: Real Zeros of Polynomials
13.5.	Algebraische Zahlen: Mathematische Grundlagen und Rechnen mit reellen algebraischen Zahlen	Simon Schmidt	Susanne	H. Cohen: A course in computional algebraic number theory 4.1-4.3 J.C. Stillwell: Elements of algebra: geometry, numbers, equations 5.1-5.5 J. Neukirch: Algebraische Zahlentheorie, I.2 A. Eigenwillig: Exact Arrangement Computation for Cubic Curves (Diplomarbeit) 2.4.4
27.5.	Resultanten und Subresultanten (Seminarvortrag)	Manuel Caroli	Nicola	Cox, Little, O'Shea: Ideals, Varieties, and Algorithms S. 149-166
3.6.	Conics	Marc Meier	Nicola Eric Berberich	Berberich et al.: A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
17.6.	Isolierende Intervalle: Sturmsche Ketten	Rico Philipp	Susanne	A. G. Akritas: Elements of Computer Algebra with Applications, 7.2; Schaback, Werner: Numerische Mathematik, 15.3; C. Yap: Fundamental Problems in Algorithmic Algebra, Chap. 7
24.6.	Approximation von Nullstellen: Newtonverfahren	Evren Ermis	Susanne	Hämmerlin, Hoffmann: Numerische Mathematik, 8.1 und 8.2 Ueberhuber: Numerical Computation 2: 14.2 Schaback, Werner: Numerische Mathematik, Kap. 8 und 9.2
1.7.	Algebraische Zahlen: Exaktes Rechnen mit Quadratwurzeln	Sebastian Altmeyer	Susanne	Mehlhorn: Circle points and predicates on circle points ; Mehlhorn: Separation bounds
8.7.	Algebraische Zahlen: Exaktes Rechnen mit Wurzeln	Sascha El-Abed	Susanne	Burnikel et al.: A separation bound for real algebraic expressions
15.7.	Nef Polyhedra	Franziska Ebert	Susanne	H. Bieri: Nef Polyhedra: A Brief Introduction. In: Computing Suppl. 10, 1995, 43-60.
22.7.	Nef Polyhedra	Bernd Mechenbier	Susanne	H. Bieri: Nef Polyhedra: A Brief Introduction. In: Computing Suppl. 10, 1995, 43-60.

Hinweise

Für das Proseminar kann man 9 Punkte (9LP) erhalten.

Der Vortrag muss eine Woche vor dem Termin der Betreuerin präsentiert werden.

Die Vorträge sollen gut verständlich sein.