Complete Adaptive Algorithms for Curves and Surfaces and their Complexity

曲线和曲面及其复杂性的完整自适应算法

• 批准号: 0728977
• 负责人: Chee Yap
• 金额: --
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728977&HistoricalAwards=false
• 关键词: Complete; Adaptive; Algorithms; Curves; Surfaces

Computational problems of curves and surfaces arise in many applications, including geometric modeling, graphics and visualization, engineering design and simulations. Most computational approaches to curves and surfaces fall under one of two viewpoints, called the Algebraic Approach and the Geometric Approach (respectively). The former approach leads to exact and complete algorithms, but these are usually inefficient and hard to implement. In the Geometric Approach, one avoids powerful algebraic techniques, in favor of numerical and simple subdivision methods. These are easier to implement, but more importantly, their complexity is adaptive, meaning that the complexity strongly depends on the input instances. Moreover, input instances with high complexity are atypical. For these reasons, most implementors prefer the Geometric Approach. Unfortunately, geometric algorithms are usually nonrobust, incomplete and have no guaranteed topological properties. Indeed, achieving robust geometric algorithms for curves and surfaces is widely viewed as the major open problem of geometric modeling. Recently, some robust adaptive algorithms for meshing curves and surfaces have been proposed, but some non-degeneracy conditions (e.g., non-singularity) remain.This research addresses several basic problems within the Geometric Approach, including the intersection of curves and surfaces, and meshing of implicit surfaces. The achieved results represent two fundamental advances in the theory of algorithms: (1) For the first time, complete and fully adaptive algorithms for such problems have been constructed. The key to such algorithms is the judicious application of zero bounds, or their geometric analogues. (2) The complexity analysis of some adaptive algorithms for meshing is initiated. The analysis introduces novel amortization arguments, and suitable concepts of precision-sensitivity. This represents a new frontier in the analysis of algorithms. Both advances build upon the principal investigator's prior work in Exact Geometric Computation, and in the implementation of the open-source Core Library software. The new adaptive algorithms are validated via implementation in Core Library.

曲线和曲面的计算问题出现在许多应用中，包括几何建模、图形和可视化、工程设计和模拟。 大多数曲线和曲面的计算方法都属于两种观点之一，分别称为代数方法和几何方法。 前一种方法可以产生精确且完整的算法，但通常效率低下且难以实现。 在几何方法中，人们避免使用强大的代数技术，而倾向于数值和简单的细分方法。 这些更容易实现，但更重要的是，它们的复杂性是自适应的，这意味着复杂性很大程度上取决于输入实例。 此外，具有高复杂性的输入实例是不典型的。 由于这些原因，大多数实施者更喜欢几何方法。 不幸的是，几何算法通常不稳健、不完整并且没有保证的拓扑特性。 事实上，实现曲线和曲面的稳健几何算法被广泛视为几何建模的主要开放问题。 最近，已经提出了一些用于啮合曲线和曲面的鲁棒自适应算法，但仍然存在一些非简并条件（例如非奇异性）。这项研究解决了几何方法中的几个基本问​​题，包括曲线和曲面的相交，以及隐式曲面的网格划分。 所取得的成果代表了算法理论的两个基本进步：（1）首次构建了针对此类问题的完整且完全自适应的算法。 此类算法的关键是明智地应用零界或其几何类似物。 (2)对部分自适应网格划分算法进行了复杂度分析。 该分析引入了新颖的摊销论点和适当的精度敏感性概念。 这代表了算法分析的新领域。 这两项进展都建立在首席研究员之前在精确几何计算和开源核心库软件实施方面的工作基础上。 新的自适应算法通过核心库中的实现进行了验证。