Dynamic aspects in computational geometry

TitelDynamic aspects in computational geometry
Publication TypeConference Paper
Year of Publication2000
AuthorsRichter-Gebert, J., & Kortenkamp U.
EditorMontes, A.
Conference NameProceedings of the EACA 2000
Conference LocationBarcelona

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.

Go to top