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.