Design, analysis, and implementation of efficient and reliable algorithms for complex geometric objects

点击翻译按钮获取中文摘要

The proposed research concentrates on the design and development of efficient algorithms to handle complex geometric objects with quality guarantees. Algorithms of this kind constitute an important basis for applications in Computer Aided Design, robotics or computer vision. Our overall philosophy requires that our solutions cope with any input and that the output matches the mathematically exact result. Moreover, we request two-fold efficiency: While we aim at proving low complexity of our algorithms, we also want them to compete with existing non-reliable software on inputs that can be handled by these implementations. That is, the runtime should adaptively depend on the difficulty of the input. It is a challenge to achieve reliability and efficiency simultaneously. A canonical way to tackle degenerate situations is by means of computer algebra methods (Gröbner bases, resultants, etc.) based on exact symbolic computations. Although constituting powerful tools, their efficiency suffers from several drawbacks such as coefficient blowups during computation, non-adaptiveness and difficulties in parallelizing the computation. By combining fast approximate with exact symbolic methods we expect adaptiveness as well as a significant speed up of the overall approach. We want to achieve this by the development of adaptive root separation and perturbation bounds for univariate polynomials and polynomial systems based on additional information gained from the approximate computation. Furthermore, the number of costly symbolic computation steps over integers should be reduced or replaced by modular computations.