AF: Medium: Collaborative Research: Approximate Computational Geometry via Controlled Linear Perturbation

研究人员将开发一种与算法无关、准确且快速的近似计算几何。 几何谓词计算和元素构造将使用浮点运算近似执行。 退化将被透明地处理。 评估和构建技术将被封装在一个软件库中，该软件库将免费供非营利组织使用。研究的挑战是鲁棒性：对于给定输入的小扰动，近似算法的输出必须是正确的。 这个定义扩展了稳定算法的数值分析定义，以涵盖组合误差。 鲁棒性是一个基本的计算机科学问题，是计算几何中的一个主要挑战。 计算几何中的主要策略，使用代数几何的精确计算，具有高计算复杂性，并且与具有误差界的近似计算的标准科学和工程策略相矛盾。 研究人员将调整近似计算的特殊需要的计算几何，这主要是组合。 该任务涉及计算几何和数值计算之间接口的核心研究。稳健的近似计算将改变计算几何的教学方式，算法的开发和实施方式，以及该领域如何与更广泛的科学和工程界互动。 介绍性课程将提出一个严格的，实用的鲁棒性理论，而不是在一个特设的，不完整的方式处理鲁棒性。 程序员将实现真实的RAM算法，使用我们的库来确保鲁棒性和处理退化，而不是为每个算法重新解决这些问题，这通常是一个主要的研究挑战。 计算几何将以高质量软件库的形式提供给其他学科，类似于现代应用数学库。

The investigators will develop an approximate computational geometry that is algorithm independent, accurate, and fast. Geometric predicate evaluation and element construction will be performed approximately using floating point arithmetic. Degeneracy will be handled transparently. The evaluation and construction techniques will be encapsulated in a software library that will be free for nonprofit use.The research challenge is robustness: the output of an approximate algorithm must be correct for a small perturbation of the given input. This definition extends the numerical analysis definition of a stable algorithm to cover combinatorial error. Robustness is a fundamental computer science problem that is a major challenge in computational geometry. The predominant strategy in computational geometry, exact computation using algebraic geometry, has high computational complexity and contradicts the standard scientific and engineering strategy of approximate computation with error bounds. The investigators will adapt approximate computation to the special needs of computational geometry, which is primarily combinatorial. This task involves core research at the interface between computational geometry and numerical computing.Robust approximate computation will transform how computational geometry is taught, how algorithms are developed and implemented, and how the field interacts with the wider scientific and engineering community. Introductory courses will present a rigorous, practical robustness theory, instead of treating robustness in an ad hoc, incomplete way. Programmers will implement real RAM algorithms as stated, using our library to ensure robustness and to handle degeneracy, instead of addressing these problems anew for every algorithm, which is often a major research challenge. Computational geometry will be available to other disciplines in the form of high-quality software libraries, akin to modern applied mathematics libraries.