Complete Adaptive Algorithms for Curves and Surfaces and their Complexity

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

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.