@conference {RicKor-DGGM-2002, title = {Dynamische {G}eometrie: {G}rundlagen und {M}{\"o}glichkeiten}, booktitle = {Tagungsband zum N{\"u}rnberger Kolloquium zur Didaktik der Mathematik 2002}, year = {2002}, pages = {369-372}, keywords = {invited}, url = {http://www.cinderella.de/papers/DG\_GM.pdf}, author = {Richter-Gebert, J{\"u}rgen and Kortenkamp, Ulrich}, editor = {Weth, Thomas} } @conference {KorRic-DCDG-2001, title = {Decision complexity in {D}ynamic {G}eometry}, booktitle = {Proceedings of ADG 2000}, series = {Lecture Notes in Artificial Intelligence}, number = {2061}, year = {2001}, pages = {167{\textendash}172}, publisher = {Springer-Verlag}, organization = {Springer-Verlag}, address = {Heidelberg}, abstract = {

Geometric straight-line programs [5,8] can be used to model geometric constructions and their implicit ambiguities. In this paper we discuss the complexity of deciding whether two instances of the same geometric straight-line program are connected by a continuous path, the Complex Reachability Problem.

}, keywords = {refereed}, url = {http://kortenkamps.net/papers/2001/36_DecisionComplexity.pdf}, author = {Kortenkamp, Ulrich and Richter-Gebert, J{\"u}rgen}, editor = {Wang, Dongming} } @conference {RicKor-DSEG-2001, title = {A dynamic setup for elementary geometry}, booktitle = {Proceedings of MTCM 2000}, year = {2001}, publisher = {Springer-Verlag}, organization = {Springer-Verlag}, abstract = {

In this article we survey the theoretical background that is required to build a consistent and continuous setup of dynamic elementary geometry. Unlike in static elementary geometry in dynamic elementary geometry the elements of a construction are allowed to move around as long as the geometric constraints intended by the construction are not violated. A typical problem in such a scenario is to resolve ambiguous situations that arise from geometric operations like intersecting a circle and a line. After introducing a formal framework for dealing with dynamic geometric constructions, we will demonstrate that a suitable resolution of these ambiguities requires the consideration of complex projective spaces. We will discuss several aspects where one can benefit from such a rather general approach. Finally, we will sketch some proofs that show that several fundamental algorithmic problems arising in such a context are NP-hard or even harder.

}, keywords = {refereed}, url = {http://kortenkamps.net/papers/2001/35\_DynamicSetup.pdf}, author = {Richter-Gebert, J{\"u}rgen and Kortenkamp, Ulrich} } @conference {KorRic-DCDG-2000, title = {Decision complexity in {D}ynamic {G}eometry}, booktitle = {Proceedings of ADG 2000}, series = {International Workshop on Automatic Deduction in Geometry}, volume = {3}, year = {2000}, note = {Extended Abstract}, pages = {216{\textendash}220}, abstract = {

Geometric straight-line programs [6, 10] can be used to model geo- metric constructions and their implicit ambiguities. In this paper we discuss the complexity of deciding whether two instances of the same geometric straight-line program are connected by a continuous path, the Complex Reachability Problem.

}, keywords = {refereed}, url = {http://kortenkamps.net/papers/2000/ADG2000_UK.pdf}, author = {Kortenkamp, Ulrich and Richter-Gebert, J{\"u}rgen}, editor = {Wang, Dongming} } @book {RicH.K-IGC-2000, title = {Die interaktive {G}eometry-{S}oftware {C}inderella}, year = {2000}, note = {German translation}, publisher = {Springer-Verlag}, organization = {Springer-Verlag}, address = {Heidelberg}, keywords = {software}, author = {Richter-Gebert, J{\"u}rgen and H.~Kortenkamp, Ulrich} } @conference {RicKor-DACG-2000, title = {Dynamic aspects in computational geometry}, booktitle = {Proceedings of the EACA 2000}, year = {2000}, pages = {51{\textendash}61}, address = {Barcelona}, abstract = {

Computational Geometry very often focuses on static problems, like computing the convex hull or Voronoi complex of a given set of points. Fundamentally new questions arise when the objects under consideration are no longer static, but may move around with respect to certain constraints. This scenario is not unusual, for instance every mechanism can be considered as a dynamic geometry entity. Here we focus on the new areas of problems that arise from genuinely dynamic effects. Constructions from elementary geometry play a crucial role in this context, since they form first natural instances of non-trivial examples where it is reasonable to study the dynamic behaviour. One of the most fundamental problems arises when one considers one point of an intersection of a line and a circle and allows the line to move around. Since the point of intersection is not unique, a computer program has to decide for every "discrete snapshot" which of the two intersection points is meant. If this decision is not made correctly a "path-jumping" of the point may occur. A careful analysis of the situation shows that for a satisfactory resolution of the problem one has to embed the configuration in an ambient complex projective space. One even has to take monodromy effects and underlying Riemann surfaces into account. We will develop a theory for the study of these phenomena. After this, we will investigate the algorithmic complexity of "making the right decision". It will turn out that even in very weak versions this problem is NP-hard. In some stronger versions it is PSPACE hard or even undecidable.

}, keywords = {refereed}, author = {Richter-Gebert, J{\"u}rgen and Kortenkamp, Ulrich}, editor = {Montes, Antonio} } @inbook {KorRic-C-1999, title = {Das {C}inderella-{P}rojekt}, booktitle = {Erfahrungen mit Java}, year = {1999}, pages = {381{\textendash}401}, publisher = {dpunkt.verlag}, organization = {dpunkt.verlag}, chapter = {17}, address = {Heidelberg}, keywords = {refereed}, url = {http://www.amazon.de/exec/obidos/ASIN/3932588339/theinteractive07}, author = {Kortenkamp, Ulrich H. and Richter-Gebert, J{\"u}rgen}, editor = {Maffeis, Silvano and Toenniessen, Fridtjof and Zeidler, Christian} } @conference {RicKor-DGPC-1999, title = {Dynamic Geometry {I}: The Problem of Continuity}, booktitle = {Abstracts 15th European Workshop Comput. Geom.}, year = {1999}, pages = {51{\textendash}53}, publisher = {INRIA Sophia-Antipolis}, organization = {INRIA Sophia-Antipolis}, keywords = {refereed}, url = {http://www.cinderella.de/papers/antibes-1.pdf}, author = {Richter-Gebert, J{\"u}rgen and Kortenkamp, Ulrich H.} } @conference {KorRic-DGA-1999, title = {Dynamic Geometry {II}: Applications}, booktitle = {Abstracts 15th European Workshop Comput. Geom.}, year = {1999}, pages = {109{\textendash}111}, publisher = {INRIA Sophia-Antipolis}, organization = {INRIA Sophia-Antipolis}, keywords = {refereed}, url = {http://cinderella.de/papers/antibes-2.pdf}, author = {Kortenkamp, Ulrich H. and Richter-Gebert, J{\"u}rgen} }