Tracing-problems in dynamic geometry

Abstract

Dynamic Geometry is the field of interactively doing geometric constructions using a computer. Usually, the classical ruler-and-compass constructions are considered. The available tools are simulated by the computer. A Dynamic Geometry System is a system to do geometric constructions that has a drag mode. In the drag mode, geometric elements with at least one degree of freedom can be moved, and the remaining part of the geometric construction adjusts automatically. Thus, the computer has to trace the paths of the involved geometric objects during the motion. In this thesis, we focus on the beautiful model by Kortenkamp and Richter-Gebert that is the foundation of the geometry software Cinderella. We embed an algebraic variant of this model into different fields of pure and applied mathematics, which leads to different approaches for realizing the drag mode practically. We develop a numerical method to solve the Tracing Problem that is based on a generic Predictor- Corrector method. Like most numerical methods, this method cannot guarantee the correctness of the computed solution curve, hence ambiguities are not treated satisfactorily. To overcome this problem, we develope a second algorithm that uses interval analysis. This algorithm is robust, and the computed step length is small enough to break up all ambiguities. Critical points are bypassed by detours, where the geometric objects or the corresponding variables in the algebraic model can have complex coordinates. Here, the final configuration depends essentially on the chosen detour, but this procedure due to Kortenkamp and Richter-Gebert leads to a consistent treatment of degeneracies. We investigate the connection of the used model for Dynamic Geometry to Riemann surfaces of algebraic functions.

Unter dynamischer Geometrie versteht man das interaktive Erstellen von geometrischen Konstruktionen am Computer. Ein Dynamisches Geometrie System ist ein Geometriesystem, in dem es möglich ist, geometrische Konstruktionen durchzuführen, und das einen Zugmodus hat. Im Zugmodus können geometrische Objekte, die mindesten einen Freiheitsgrad haben, mit der Maus bewegt werden. Dabei paßt sich die gesamte geometrische Konstruktion der Bewegung an, indem der Computer das entstehende Pfadverfolgungsproblem löst. In dem von uns verwendeten Modell für dynamische Geometrie steht die Stetigkeit der resultierenden Bewegungen im Vordergrund, es wurde von Kortenkamp und Richter- Gebert entwickelt und ist die Grundlage für die Geometriesoftware Cinderella. Wir arbeiten den Zusammenhang dieses Modells zu Riemannschen Flächen algebraischer Funktionen heraus. Im Rahmen dieser Doktorarbeit zeigen wir, wie sich eine algebraische Variante des Modells für Dynamische Geometrie von Kortenkamp und Richter-Gebert sowohl in die angewandte als auch in die reine Mathematik einfügt. Daraus resultiert ein numerisches Verfahren für das Tracing Problem, das auf einer allgemeinen Prediktor-Korrektor-Methode aufbaut. Wie bei den meisten numerischen Verfahren gibt es hierbei keine Garantie dafür, dass die Schrittweite klein genug gewählt ist, um auf dem richtigen Lösungsweg zu bleiben. Das bedeutet, dass ein korrekter Umgang mit Mehrdeutigkeiten nicht garantiert werden kann. Wir haben einen weiteren Algorithmus entwickelt, bei dem die Schrittweite mit Hilfe von Intervallrechnung so gew\"ahlt wird, dass die Korrektheit der Lösung garantiert ist. Kritische Punkte werden durch Umwege umgangen, bei denen die geometrischen Objekte bzw.~die entsprechenden Variablen in einem algebraischen Modell komplexe Koordinaten haben können. Dabei hängt die erreichte Konfiguration wesentlich von dem gewählten Umweg ab. Diese Idee von Kortenkamp und Richter-Gebert führt zu einer konsistenten Behandlung von kritischen Punkten und kommt in der interaktiven Geometriesoftware Cinderella zum Einsatz.