Robust and efficient software for problems in 2.5-dimensional non-linear geometry : algorithms and implementations

Abstract

We discuss how to compute and implement three geometric problems dealing with nonlinear three-dimensional surfaces. As a main tool we rely on planar subdivisions induced by algebraic curves, developed in CGAL (Computational Geometry Algorithm Library). First, we achieve lower envelopes of quadrics using CGAL'S Envelope_3 package. Second, we extend CGAL's Arrangement_2 package to support two-dimensional arrangements on a parametric reference surface. Two main examples are discussed: Arrangements induced by algebraic surfaces on an elliptic quadric and on a ring Dupin cyclide. Third, we decompose a set of quadrics or a set of algebraic surfaces into cells using projection. Our goal is to achieve topological information for the surfaces, while preserving their geometric properties. We maintain a special two-dimensional arrangement; the lifting to the third dimension benefits from the recently presented bitstream Descartes method. The obtained cell decomposition supports a set of other geometric applications on surfaces. Our implementations follow the geometric programming paradigm. That is, we split combinatorial tasks from geometric operations by generic programming techniques. It is also ensured that each geometric predicate returns the mathematically correct result, even if it internally exploits approximative methods to speed up the computation. The thesis is written in English.

Wir besprechen die Berechnung und Implementierung dreier Probleme aus der algorithmischen Geometrie, deren Eingabe aus gekrümmten Oberflächen besteht. Als Werkzeug benutzen wir in CGAL (Computational Geometry Algorithm Library) entwickelte Zerlegungen der Ebene durch algebraische Kurven. Zunächst berechnen wir die untere Einhüllende einer Menge von Quadriken. Danach erweitern wir CGALs Arrangement_2 Paket, so dass zweidimensionale Zerlegungen auf para-meterisierbaren Oberflächen berechnet werden können, und führen zwei konkrete Beispiele aus: Zerlegungen induziert durch algebraische Oberflächen auf einer Quadrik und auf einem ringförmigen Zykliden nach Dupin. Zum Abschluss unterteilen wir eine Menge von Quadriken bzw. algebraischen Oberflächen in disjunkte Untermannigfaltigkeiten mit Hilfe einer Projektion. Die Hebung erfolgt mit einem kürzlich vorgestellten approximativen Verfahren zur Nullstellenisolation (bitstream Descartes). Ingesamt erhalten wir geometrische Eigenschaften der Eingabe und erfahren mehr über deren topologische Zusammensetzung. Die kombinatorische Ausgabe hilft bei der Berechnung anderer geometrischer Probleme auf den Oberflächen. Unsere Implementierungen trennen kombinatorische Aufgaben von geometrischen durch Anwenden von generischen Programmiertechniken. Wir stellen außerdem sicher, dass Prädikate stets das mathematisch korrekte Ergebnis ausgeben, auch wenn sie intern mit approximativen Methoden rechnen. Die Arbeit ist in englischer Sprache verfasst.