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.