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.

该建议涉及三维空间中表面研究的计算方面。结识别问题是此类问题的一个关键示例，它寻求一个程序，以确定何时可以将三个空间中的两条曲线彼此变形。它的计算复杂性是运行这种算法所需的步骤数，仍然尚未完全了解。对这个问题的研究表明，复杂性理论，低维拓扑结构之间的有趣和意外的联系，跨越曲线的表面需要多少面积的问题（差异几何形状的问题）以及有关如何用三角形构造表面的问题，以尽可能少的三角形构建表面。调查人员计划表明，这个问题已经在称为NP的一类问题中，也在称为Conp的类中。他进一步旨在改善因此和相关问题所知的运行时间的上限和下限，并探索与计算和差异几何形状的联系。三维流形以及我们所生活的世界中所包含的对象中包含的表面。他们所居住的世界。他们的数学理论既自然又适用。 计算问题在这些领域的调查中起着越来越多的作用。计算复杂性，理论计算机科学领域，研究算法及其运行时间。许多重要的算法具有几何成分，几何方法可以导致对有效计算的见解。起源于拓扑和几何形状的技术导致了计算机图形，可视化，医学和分子建模以及图像识别的算法。 该提案中考虑的问题涉及构建算法以分析几何对象的性质，以及对这些算法的计算复杂性的分析。