Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Jürgen Richter-Gebert
The complex behavior of geometric objects
Geometric constructions (e.g. with ruler and compass) play a central role in geometry. While static aspects of these constructions have been widely explored, dynamic aspects have been hardly investigated. This talk focuses on the effects that arise when one allows the base elements of a construction to move. In particular we discuss the consequences of the following natural continuity requirement: "a continuous movement of base elements should induce a continuous movement of the dependent elements."
In the first part of this talk it will be demonstrated that the only way to satisfy this requirement is to extend the geometric framework and study geometric objects in complex projective spaces. Configuration spaces of constructions then lead in a natural way to the study of Riemann surfaces.
The second part of the talk investigates complexity theoretic aspects that arise in this context: "What is the algorithmic complexity to actually trace the dependent elements of a concrete construction". It turns out that this problem is already NP-hard and therefore intractable. Seemingly weaker questions that ask for the mere existence of a path that takes a construction from one situation to another turn out to be PSPACE-hard or even undecidable.
The talk will contain demonstrations with the dynamic geometry program Cinderella whose implementation is based on these new insights in elementary geometric constructions.
Back
