Computational Topology for Surface Approximation

这项研究考察了在工程设计、动画和分子建模中使用的算法确保对象的基本形状保持的广泛问题。虽然可以客观地测量和比较两个物体的几何特征，如表面积和体积，但其他形状特征，如花园软管和打结的同一软管之间的区别，更加微妙，需要本研究的方法。令人惊讶的是，对于目前的算法来说，这些差异并不容易，而且在航空和汽车行业，检测这些差异的困难估计每年会造成数十亿美元的生产力损失。这项研究是计算机科学家和数学家之间的跨学科调查，相应的教育重点是向下一代科学家介绍将理论与新颖的工程和生命科学应用相结合的整体视角。该研究将新的拓扑约束和数值误差界集成到几何近似算法中，定义了曲面近似何时与原始曲面处于相同的拓扑等价类。虽然曲面近似是一个经典的数学主题，但拓扑等价性的问题通常留给人类来检查。这项研究的新方法是理论和实践的发展，以创建计算上容易处理的算法，以确保丰富的曲面逼近技术的拓扑等价。创建适当的应用数学以消除对中轴计算的任何直接算法依赖，极大地丰富了提供可验证拓扑的稳健近似算法的类别。另一项重大创新是综合考虑了由有界曲面片组成的几何模型。这种观点消除了一个流行但不切实际的理论假设，即几何模型只有一个边界曲面。额外的细微之处依赖于沿每个组成部分边界的新的数值近似。

This research examines broad issues of guaranteeing that the essential shape of an object is preserved during algorithms used in engineering design, animation and molecular modeling. While geometric characteristics such as surface area and volume can be objectively measured and compared for two objects, other shape characterizations, such as the distinction between a garden hose and the same hose tied into a knot, are more subtle and require the methods of this research. Surprisingly, these distinctions are not easy for present day algorithms and difficulties in detecting these differences has been estimated to cost billions of dollars annually in lost productivity in the aeronautical and automotive industries. This research is an interdisciplinary investigation between computer scientists and mathematicians with a corresponding educational emphasis upon introducing the next generation of scientists to a holistic perspective that combines theory with novel engineering and life science applications. The applications to molecular modeling are expected to be attractive to the many women in the biological sciences and thereby increase the participation of women in the computational and mathematical sciences.This research integrates new topological constraints and numerical error bounds into geometric approximation algorithms, defining when a surface approximation is in the same topological equivalence class as the original surface. While surface approximation is a classical mathematical topic, the issue of topological equivalence has typically been left to human inspection. The novel approach of this research is the development of the theory and practice to create computationally tractable algorithms that ensure topological equivalence for a rich class of surface approximation techniques. The creation of appropriate applied mathematics to eliminate any direct algorithmic dependence upon computation of the medial axis significantly enriches the class of robust approximation algorithms delivering verifiable topology. Another major innovation is the comprehensive consideration of geometric models composed from bounded surface patches. This perspective eliminates a prevailing, but unrealistic theoretical hypothesis that geometric models have only a single bounding surface. The additional subtleties rely upon new numerical approximations along the boundaries of each constituent patch.