Dissertation : Complex Tracing
Betreuer: Prof. Dr. Helmut Alt, Dr. Ulrich Kortenkamp
Hinter den Kulissen der Geometriesoftware Cinderella verbirgt sich eine elegante mathematische Theorie, die sich aus verschiedenen Bereichen zusammensetzt. Aus ihr ergeben sich Fragen zwischen Komplexitätstheorie und Geometrie, die zum Teil noch ungelöst sind.
In Cinderella werden geometrische Konstruktionen durch geometrische Straight-Line Programme (GSP) repräsentiert. Diese setzen sich aus freien Punkten und abhängigen Elementen wie z. B.
- der Verbindungsgeraden zweier verschiedener Punkte,
- dem Schnittpunkt zweier verschiedener Geraden,
- einer der beiden Winkelhalbierenden zweier Geraden,
- einer der höchstens zwei Schnittpunkte einer Geraden mit einem Kreis
zusammen. Eine Instanz eines GSP ist eine Zuweisung von festen Werten zu allen freien Punkten und Wahlen. Ein GSP entspricht also einer formalen Konstruktionsbeschreibung und eine Instanz einer konkreten Zeichnung in der Ebene.
Beispiel für ein GSP:
A | <- | FREE | \\ A ist ein freier Punkt. |
B | <- | FREE | \\ B ist ein freier Punkt. |
C | <- | FREE | \\ C ist ein freier Punkt. |
p | <- | JOIN(A,B) | \\ p ist die Gerade durch A und B. |
q | <- | JOIN(A,c) | \\ q ist die Gerade durch A und C. |
r | <- | BISECT(p,q) | \\ r ist Winkelhalbierende von p und q. |
Abbildung 1 zeigt drei Instanzen dieses GSPs. Man sieht leicht, daß die linke Instanz ,,stetig`` in die rechte überführt werden kann (s. Abb. 2).
Im allgemeinen ist es jedoch nicht immer möglich, eine vorgegebene Instanz ,,stetig`` in eine weitere vorgegebene Instanz zu überführen. In 16#16 wird gezeigt, daß das sogenannte ,,Reachability Problem`` NP-schwer ist.
Die Komplexität des selben Problems im Komplexen (d.h. die Koordinaten der freien Punkte und der abhängigen Elemente dürfen Werte aus 17#17 annehmen) ist hingegen noch unbekannt.
Ein weiteres Problem ist das ,,Tracing Problem``, das mit dem Reachability Problem verwandt ist. Hier liegt die gleiche Situation vor: In 16#16 wird gezeigt, daß es im Reellen NP-schwer ist, und die Komplexität im Komplexen ist unbekannt. Das sogenannte ,,Complex Tracing`` könnte z.B. für das automatische Beweisen oder das Umgehen von Singularitäten in Cinderella verwendet werden.
Literatur:
J. Richter-Gebert, U. Kortenkamp, Complexity Issues in Dynamic Geometry, Proceedings of the Smale Fest 2000, 2001