Complete Adaptive Algorithms for Curves and Surfaces and their Complexity

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

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.