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

Main titleComplexity issues in dynamic geometry
AuthorRichter-Gebert, Jürgen
AuthorKortenkamp, Ulrich H.
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages35 S.
Series [Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 2000,22]
Classification (DDC)516 Geometry
AbstractThis 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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2000
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-10-29 : 11:26:25
Last changed2015-02-27 : 08:25:18
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004099