Authors:	Reithmann, Tobias
Title:	Topologically correct intersection curves of tori and natural quadrics
Online publication date:	17-Jul-2009
Year of first publication:	2009
Language:	english
Abstract:	This thesis provides efficient and robust algorithms for the computation of the intersection curve between a torus and a simple surface (e.g. a plane, a natural quadric or another torus), based on algebraic and numeric methods. The algebraic part includes the classification of the topological type of the intersection curve and the detection of degenerate situations like embedded conic sections and singularities. Moreover, reference points for each connected intersection curve component are determined. The required computations are realised efficiently by solving quartic polynomials at most and exactly by using exact arithmetic. The numeric part includes algorithms for the tracing of each intersection curve component, starting from the previously computed reference points. Using interval arithmetic, accidental incorrectness like jumping between branches or the skipping of parts are prevented. Furthermore, the environments of singularities are correctly treated. Our algorithms are complete in the sense that any kind of input can be handled including degenerate and singular configurations. They are verified, since the results are topologically correct and approximate the real intersection curve up to any arbitrary given error bound. The algorithms are robust, since no human intervention is required and they are efficient in the way that the treatment of algebraic equations of high degree is avoided. Diese Arbeit liefert effiziente und robuste Algorithmen zur Berechnung der Schnittkurve zwischen einem Torus und einer einfachen Fläche (d.h. einer Ebene, einer natürlichen Quadrik oder eines weiteren Torus), basierend auf algebraischen und numerischen Methoden. Der algebraische Teil umfasst die Klassifizierung des topologischen Typus der Schnittkurve und das Auffinden von degenerierten Fällen, wie z.B. eingebettete Kegelschnitte und Singularitäten. Darüberhinaus werden Zeugenpunkte für jede zusammenhängende Schnittkurvenkomponente bestimmt. Durch das Lösen von Polynomen mit maximalem Grad von vier und durch Verwendung exakter Arithmetik werden die erforderlichen Rechnungen effizient und exakt durchgeführt. Der numerische Teil umfasst Algorithmen für die Verfolgung der Schnittkurvenkomponenten, ausgehend von den zuvor berechneten Zeugenpunkten. Durch die Verwendung von Intervall-Arithmetik werden Fehler, wie z.B. das Springen zwischen Komponenten oder das Auslassen von Kurventeilen, unterbunden. Desweiteren werden die Umgebungen von Singularitäten korrekt behandelt. Unsere Algorithmen sind komplett in dem Sinne, dass jegliche Eingabe, inklusive degenerierter und singulärer Konfigurationen, bearbeitet werden kann. Sie sind verifiziert, da die Ergebnisse topologisch korrekt sind und die eigentliche Schnittkurve bis zu jeder beliebigen Genauigkeit approximieren. Die Algorithmen sind robust, da keine Benutzerintervention erforderlich ist, und sie sind effizient, da das Bearbeiten von höhergradigen algebraischen Gleichungen vermieden wird.
DDC:	004 Informatik 004 Data processing
Institution:	Johannes Gutenberg-Universität Mainz
Department:	FB 08 Physik, Mathematik u. Informatik
Place:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-4500
URN:	urn:nbn:de:hebis:77-20370
Version:	Original work
Publication type:	Dissertation
License:	In Copyright
Information on rights of use:	https://rightsstatements.org/vocab/InC/1.0/
Appears in collections:	JGU-Publikationen