AF: Small: Subdivision Methods: Correctness and Complexity

基于细分的算法可以解决数学、计算机科学和其他科学领域的各种应用问题。例如，这些类型的算法用于计算机图形学、数学生物学、计算几何、数学建模、机器人、机器学习和数学计算。基于细分的算法很受欢迎，因为它们相对容易在计算机上描述和实现，并且在实践中通常是有效的。这个项目的工作是量化和提高这些类型的算法的有效性。通过研究效率和提供算法来近似解决通常被认为是棘手的问题，这个项目的结果提供了可以应用于整个科学领域的实际问题的技术。基于细分的算法递归地、自适应地将给定的域细分为更小的区域，直到在每个更小的区域中，可以确定特定于问题的特征的行为。基于细分的算法经常被使用，因为它们是并行的、递归的和自适应的。更准确地说，它们使用弱局部测试，只在困难特征附近执行更多细分。然而，这些特征使得基于细分的算法具有实用性，也使它们具有挑战性。例如，局部测试使全局拓扑正确性变得困难，而自适应（非统一）细分使细分的数量难以限定。本项目通过以下两种方式解决了基于细分算法的复杂度和正确性这两个重要问题：(1)使用连续摊销作为统一的方法来计算基于细分算法的复杂度。(2)发展基于拓扑证明细分的代数变种几何应用算法。该项目将连续摊销技术扩展到许多不同类型的算法，包括迭代和二维细分；此外，该项目还开发了基于细分的算法来近似以前棘手的问题，如中轴线和曲面相交。

Subdivision-based algorithms can solve problems from a wide variety of applications in mathematics, computer science, and the sciences. For example, these types of algorithms are used in computer graphics, mathematical biology, computational geometry, mathematical modeling, robotics, machine learning, and mathematical computation. Subdivision-based algorithms are popular because they are relatively easy to describe and implement on a computer, and they are often efficient in practice. The work in this project is to quantify and improve the effectiveness of these types of algorithms. By studying the efficiency and providing algorithms to approximate solutions to problems which are typically considered intractable, the results of this project provide techniques which can be applied to practical problems throughout the sciences.Subdivision-based algorithms recursively and adaptively subdivide a given domain into smaller regions until, in each smaller region, the behavior of a problem-specific feature can be determined. Subdivision-based algorithms are frequently used because they are parallelizable, recursive, and adaptive. More precisely, they use weak local tests and perform more subdivisions only near difficult features. These features that make subdivision-based algorithms practical, however, also make them challenging to study. For example, local tests make global topological correctness difficult and adaptive (non-uniform) subdivisions make the number of subdivisions difficult to bound. This project addresses both of the important questions of complexity and correctness for subdivision-based algorithms in the following two ways: (1) Using continuous amortization as a uniform method to compute the complexity of subdivision-based algorithms. (2) Developing topologically certified subdivision-based algorithms for geometric applications on algebraic varieties. This project extends the technique of continuous amortization to many different types of algorithms including iterative and two-dimensional subdivisions; additionally, the project develops subdivision-based algorithms to approximate previously intractable problems such as the medial axis and intersections of surfaces.