max planck institut
informatik
informatik
|
|
|
|
|
|
Our research focuses on the design, analysis and implementation of efficient, exact and complete geometric algorithms for complex geometric objects. Objects of interest are, for instance, (semi-)algebraic curves, surfaces and arrangements of those. We consider our algorithms as a fundamental basis for the solution of many problems in computer-aided design, geometric modeling or robotics.
We provide algorithms and corresponding implementations that are capable to handle any given input (complete) and whose output reflects the mathematical correct result (exact). Most existing implementations do not come with the latter two guarantees due to the fact that they completely rely on fast but approximate computation and that non-generic situations are not considered; Kettner et al. gave some illustrative examples (see the reference below) showing that, even for very simple geometric problems such as the convex hull computation of points in the plane, the presence of nearly degenerate situations may lead to serious errors in existing implementations.
The main challenge in the design of exact and complete algorithms is to achieve efficiency at the same time.
Why is this so difficult? The most natural approach in the design of exact and complete algorithms is to exactly compute each of the intermediate results. This means to perform algebraic computations within an extension field of the rational numbers. Unfortunately, the complexity of the corresponding representations increases tremendously after only a few iterations in a geometric algorithm, rendering a naive approach impractical. Since we want to guarantee exactness and completeness, we cannot completely avoid purely symbolic operations because essential information such as whether three curves intersect in a common point is implicitly stored by the exact algebraic representation. However, in most situations, approximate numerical computing can replace costly symbolic methods without sacrificing exactness.
Besides guaranteeing exactness and completeness, we aim to address the following main tasks: (1) Increasing the efficiency of necessary algebraic operations such as the computation of resultants, GCDs, etc., (2) Replacing symbolic computation by approximate computation whenever this is possible, and (3) Providing proofs (in theory and practice) that our methods are efficient. We address (1) by developing and implementing new methods to perform symbolic computations that suit well for highly parallelized hardware such as GPUs, (2) by introducing numerical methods which come along with additional guarantees of exactness and a novel design of the overall algorithms, and (3) by a theoretical complexity analysis and practical C++ implementation of our methods.
Our department has has an excellent reputation for publishing efficient and correct software in algorithms and data structures. Besides their practical usefulness, these implementation efforts also stimulate new and exciting research questions for our group, such as efficiency in practice compared to the O-calculus in theory and understanding of robustness and degeneracy handling in geometric algorithms. The size of our software projects often implies that we apply techniques from software engineering and, for example, develop new solutions following the object-oriented or generic programming paradigm. Our geometric software gets published within CGAL, Computational Geometry Algorithms Library, after a reviewing process that is similar to the one for a journal submission. This reviewing process ensures that the software reaches industrial strength and, thus, can be distributed and further developed by Geometry Factory. Beyond our contribution to the library we provide a demo that allows everybody to analyze algebraic curves and compute arrangements of such: Webdemo for the computation of planar arrangements
