Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25937
Titel: Robust and efficient software for problems in 2.5-dimensional non-linear geometry : algorithms and implementations
Verfasser: Berberich, Eric
Sprache: Englisch
Erscheinungsjahr: 2008
SWD-Schlagwörter: Algorithmische Geometrie
Geometrie
Oberfläche
Freie Schlagwörter: Computational Geometry Algorithm Library
CGAL
computational geometry algorithm library
geometric problems
nonlinear three-dimensional surfaces
geometric programming paradigm
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-22305
hdl:20.500.11880/25993
http://dx.doi.org/10.22028/D291-25937
Erstgutachter: Melhorn, Kurt
Tag der mündlichen Prüfung: 22-Dez-2008
SciDok-Publikation: 17-Jul-2009
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_789_Berb_Eric_2008.pdf4,97 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.