Complete Adaptive Algorithms for Curves and Surfaces and their Complexity

曲线曲面的计算问题广泛存在于几何建模、图形与可视化、工程设计与仿真等领域。大多数曲线和曲面的计算方法属于两种视点中的一种，分别称为代数法和几何法。前一种方法可以得到精确而完整的算法，但这些算法通常效率较低且难以实现。在几何方法中，人们避免使用强大的代数技术，而是采用数值和简单的细分方法。它们更容易实现，但更重要的是，它们的复杂性是自适应的，这意味着复杂性强烈依赖于输入实例。此外，具有高复杂性的输入实例是非典型的。出于这些原因，大多数实现者更喜欢几何方法。遗憾的是，几何算法通常是不健壮的、不完全的，并且没有保证的拓扑性质。事实上，实现稳健的曲线和曲面几何算法被广泛认为是几何建模的主要开放问题。近年来，人们提出了一些稳健的自适应曲线曲面网格划分算法，但仍然存在一些非退化条件(如非奇异性)，本文研究了几何方法中的几个基本问题，包括曲线曲面的求交和隐式曲面的网格划分。所取得的结果代表了算法理论的两个基本进展：(1)首次构造了这类问题的完全和完全自适应算法。这类算法的关键是明智地应用零界或它们的几何类似物。(2)对几种自适应网格划分算法进行了复杂性分析。该分析引入了新的摊销论点，以及合适的精度敏感度概念。这代表了算法分析的一个新前沿。这两项进展都建立在首席研究人员先前在精确几何计算方面的工作以及在开放源码核心图书馆软件的实施方面。通过在Core库中的实现对新的自适应算法进行了验证。

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.