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

复杂几何对象高效可靠算法的设计、分析和实现

• 批准号: 171335636
• 负责人: Dr. Michael Sagraloff
• 金额: --
• 依托单位: Max-Planck-Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2010
• 资助国家: 德国
• 起止时间: 2009-12-31 至 2012-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/171335636?language=en
• 关键词: Design; analysis; implementation; efficient; reliable

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.

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