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

建议的研究集中在设计和开发高效的算法来处理复杂的几何对象的质量保证。这种算法构成了计算机辅助设计，机器人或计算机视觉应用的重要基础。我们的总体理念要求我们的解决方案科普任何输入，并且输出与数学上精确的结果相匹配。此外，我们要求双重效率：虽然我们的目标是证明我们的算法的低复杂性，但我们也希望它们在这些实现可以处理的输入上与现有的不可靠软件竞争。也就是说，运行时应该自适应地依赖于输入的难度。同时实现可靠性和效率是一个挑战。处理退化情况的一个典型方法是通过计算机代数方法（Gröbner基，结式等）。基于精确的符号计算虽然构成强大的工具，其效率遭受的几个缺点，如系数爆破在计算过程中，非自适应性和困难的并行计算。通过将快速近似与精确符号方法相结合，我们期望自适应性以及整体方法的显着加速。我们要实现这一目标的发展自适应根分离和扰动界的一元多项式和多项式系统的基础上获得的额外信息的近似计算。此外，整数上昂贵的符号计算步骤的数量应该减少或由模计算取代。

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.