Complexity of algorithms in low-dimensional topology

低维拓扑算法的复杂性

• 批准号: 0306602
• 负责人: Joel Hass
• 金额: $ 13.95万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306602&HistoricalAwards=false
• 关键词: Complexity; algorithms; low; dimensional; topology

This proposal concerns computational aspects of the study of surfaces in three dimensional space. The Knot Recognition Problem, a key example of such problems, seeks a procedure to determine when two curves in 3-space can be deformed to one another. Its computational complexity, the number of steps required to run such an algorithm, is still not completely understood. Investigations into this problem have revealed intriguing and unexpected connections between complexity theory, low-dimensional topology, the question of how much area is required of a surface spanning a curve (a problem in differential geometry), and questions concerning how to construct surfaces with as few triangles as possible (part of computational geometry). The investigator plans to show that this problem, already known to be in a class of problems called NP, is also in a class called coNP. He further aims to improve both upper and lower bounds on the running times known for this and related problems, and to explore connections to computational and differential geometry.Three dimensional manifolds and the surfaces contained in them model objects that are found in the world we live in. Their mathematical theory is both natural and widely applicable. Computational issues are playing an increasing role in investigations in these areas. Computational complexity, a field in theoretical computer science, studies algorithms and their running times. Many important algorithms have geometric components, and geometric methods can lead to insights into efficient computation. Techniques originating in topology and geometry have led to improved algorithms in computer graphics, visualization, medical and molecular modeling and image recognition. The problems considered in this proposal concern the construction of algorithms to analyze the nature of geometrical objects, and the analysis of the computational complexity of these algorithms.

该建议涉及三维空间中曲面研究的计算方面。纽结识别问题，这类问题的一个重要例子，寻求一个过程，以确定何时在3空间中的两条曲线可以变形到另一个。它的计算复杂性，运行这样一个算法所需的步骤数量，仍然没有完全理解。对这个问题的研究揭示了复杂性理论、低维拓扑、曲面需要多大面积的问题（微分几何中的一个问题）和如何用尽可能少的三角形构造曲面的问题（计算几何的一部分）之间有趣而意想不到的联系。研究人员计划证明，这个问题，已经知道是在一类问题称为NP，也是在一类称为coNP。他进一步的目标是提高这一问题和相关问题的运行时间的上限和下限，并探索与计算几何和微分几何的联系。三维流形和其中包含的曲面模拟了我们生活的世界中的物体。他们的数学理论既自然又广泛适用。 计算问题在这些领域的调查中发挥着越来越大的作用。计算复杂性是理论计算机科学的一个领域，研究算法及其运行时间。许多重要的算法都有几何成分，几何方法可以帮助我们理解高效的计算。源自拓扑学和几何学的技术已经导致计算机图形学、可视化、医学和分子建模以及图像识别中的改进算法。 在这个建议中考虑的问题涉及的算法来分析几何对象的性质，并分析这些算法的计算复杂性的建设。