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算法，使用我们的库来确保健壮性和处理简并性，而不是为每个算法重新解决这些问题，这通常是一个主要的研究挑战。计算几何将以高质量软件库的形式提供给其他学科，类似于现代应用数学库。