Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Complexity issues in dynamic geometry
Richter-Gebert, Jürgen ;  Kortenkamp, Ulrich H. ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelComplexity issues in dynamic geometry
AutorRichter-Gebert, Jürgen
AutorKortenkamp, Ulrich H.
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl35 S.
Schriftenreihe [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 2000,22]
DDC516 Geometrie
ZusammenfassungThis article deals with the intrinsic complexity of tracing and reachability questions in the context of elementary geometric constructions. We consider constructions from elementary geometry as "dynamic entities": while the free points of a construction
perform a continuous motion the dependent points should move consistently and continuously.
We focus on constructions that are entirely built up from "join", "meet" and "angular
bisector" operations. In particular the last operation introduces an intrinsic ambiguity: Two
intersecting lines have two different angular bisectors. Under the requirement of continuity
it is a fundamental algorithmic problem to resolve this ambiguity properly during motions
of the free elements.

After formalizing this intuitive setup we prove the following main results of this article:
- It is NP-hard to trace the dependent elements in such a construction.
- It is NP-hard to decide whether two instances of the same construction lie in the
same component of the configuration space.
- The last problem becomes PSPACE-hard if we allow one additional sidedness test
which has to be satisfied during the entire motion.

On the one hand the results have practical relevance for the implementations of Dynamic
Geometry Systems. On the other hand the results can be interpreted as statements
concerning the intrinsic complexity of analytic continuation.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr2000
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am29.10.2009 - 11:26:25
Letzte Änderung23.01.2014 - 16:21:36
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004099
Zugriffsstatistik
 

LOADING...