Geometrisches Runden und Vereinfachen und Grundlagen exakten geometrischen Rechnens mit algebraischen Zahlen
Final Report Abstract
Das Implementieren geometrischer Algorithmen ist bekanntermaßen eine schwierige Aufgabe. Neben der Kompliziertheit mancher in der Algorithmischen Geometrie entwickelter Algorithmen liegt der Hauptgrund in der Diskrepanz zwischen dem bei Entwurf und Korrektheitsbeweis auf theoretischer Seite zugrunde gelegten Maschinenmodell und den in Anwendungen in der Praxis zur Verfügung stehenden realen Maschinen (Prozessor plus Betriebssystem plus Programmiersprache) in Bezug auf Rechengenauigkeit. In der Theorie nimmt man an, dass man mit beliebigen reellen Zahlen exakt rechnen kann, in der Praxis wird reelle Arithmetik wie in vielen Bereichen des wissenschaftlichen Rechnens durch hardwareunterstü tzte und daher sehr schnelle, aber andererseits inherent rundungsfehlerbehaftete Gleitkommaarithmetik ersetzt. Rundungsfehlerbedingte Inkonsistenzen in den Berechnungen führen dann mehr oder weniger oft zu Programmabstürzen oder katastrophal falschen, weil geometrisch unmöglichen Ergebnissen. In der Algorithmischen Geometrie wurden verschiedene Ansätze zum Lösen dieses Problems verfolgt. Unter diesen hat sich der Ansatz, geometrisch exakt zu rechnen, d.h., sicherzustellen, dass alle Verzweigungen im Programmablauf korrekt sind, als sehr tragfähig erwiesen, ganz im Gegensatz zu dem Ansatz, bei Vergleichstest im Programmcode solange mit geratenen Epsilons "herumzuexperimentieren", bis genügend viele der vorhandenen Beispieleingaben bearbeitet werden können, ohne dass das Programm abstürzt. Vielfach verlangen die Techniken, die zum effizienten geometrisch exakten Rechnen in der Algorithmischen Geometrie entwickelt wurden, vom Implementierer ein tiefes Verstä ndnis der zugrunde liegenden algebraischen und numerischen Zusammenhänge. Ein wichtiger Schritt in Richtung Benutzerfreundlichkeit beim geometrisch exakten Rechnen ist die Bereitstellung von Zahltypen, die genau so wie Gleitkommazahlen eingesetzt werden können, aber garantiert korrekte Vergleichsresultate liefern. Der Implementierer geometrischer Algorithmen, der auf diese Zahltypen zurückgreift, muss nichts über die internen Abläufe in den Zahltypen wissen. Dies hat allerdings seinen Preis. Der so erzeugte Code ist weniger effizient als Code, der mit Hilfe spezieller, aber weniger benutzerfreundlicher, d.h., implementiererfreundlicher, Techniken erzeugt wurde. Korrekte Vergleichsresultate lassen sich für algebraische Berechnungen durch iteriertes Berechnen immer besserer Approximationen erzielen. Dank sogenannter Separationsschranken kann so auch auf Null getestet werden. Um falls nötig bessere Approximationen nachberechnen zu können, wird die Entstehungeschichte numerischer Werte in gerichteten azyklischen Graphen verwaltet. Im Projekt "Exaktes Geometrisches Rechnen und Runden" haben wir wesentliche Fortschritte hin zu einem effizienteren und benutzerfreundlicheren geometrisch exakten Rechnen erzielt. Wir haben neue Techniken entwickelt und vorhandene mit neuen kombiniert, und so die Effizienz von benutzerfreundlichem, geometrisch exaktem Rechnen gesteigert. Ferner haben wir einen neuen auf gerichteten azyklischen Graphen basierenden Zahltyp generisch entworfen und implementiert. Die Generiziät des neuen Zahltyps wird es uns wesentlich erleichtern, zu Testzwecken Bausteine des Zahltyps auszutauschen und so nach den in der Praxis performantesten Lösungen zu suchen.
Publications
-
Experimental Comparison of the Cost of Approximate and Exact Convex Hull Computation in the Plane. In CCCG, 2006
Stefan Schirra and Jan Tusch
-
On the Design and Performance of Reliable Geometric Predicates Using Error-free Transformations and Exact Sign of Sum Algorithms. In Prosenjit Bose, editor, CCCG, pages 45–48. Carleton University, Ottawa, Canada, 2007
Marc Mörig and Stefan Schirra
-
How Reliable are Practical Point-in-polygon Strategies? In Dan Halperin and Kurt Mehlhorn, editors, ESA, volume 5193 of Lecture Notes in Computer Science, pages 744–755. Springer, 2008
Stefan Schirra
