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

AF：媒介：协作研究：通过受控线性扰动近似计算几何

• 批准号: 0904832
• 负责人: Elisha Sacks
• 金额: $ 30万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0904832&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Approximate

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.

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