Efficient Triangulations, Decision Problems & Algorithms

高效的三角测量、决策问题

• 批准号: 0505609
• 负责人: William Jaco
• 金额: $ 11.75万
• 依托单位: Oklahoma State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-15 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0505609&HistoricalAwards=false
• 关键词: Efficient; Triangulations; Decision; Problems; Algorithms

The principal thrust of this research project is further development of efficient triangulations and their applications to the study and understanding of 3-manifolds. 0- and 1-efficient triangulations have lead to a number of new methods and results on triangulations of 3-manifolds, decision problems, algorithms, computational complexity, Heegaard splittings, and Dehn fillings. We propose to develop further our understanding of 0- and 1-efficient triangulations and to form a notion of g-efficient triangulations (g 1). Our goals are to make an explicit connection between efficient triangulations and geometric structures on 3-manifolds, to use efficient triangulations for a better understanding of Heegaard splittings of 3-manifolds, and to use our methods that reduce a given triangulation to an efficient triangulation to achieve a simplification to the solution of the Homeomorphism Problem for 3-manifolds (Classification of 3-manifolds). In particular, we propose new algorithms for deciding if a 3-manifold is a Haken manifold, for the JSJ decomposition of a 3-manifold and for the recognition of Haken manifolds.Three-dimensional manifolds are mathematical objects which are locally modeled on familiar three-dimensional space. The major problem in the study of three-manifolds is their classification, which is to make a complete list of all three-manifolds without duplications. The study and understanding of three-manifolds toward such a classification is the main objective of this project. In particular, we know that three-manifolds can be considered as a union of building blocks fitting together in a very organized way. For example, tetrahedra may be used as the building blocks; in this case, the collection of tetrahedra and the information about how they fit together is called a triangulation of the three-manifold. All three-manifolds can be triangulated. Thus one of the major strategies toward solving the classification problem is to find methods to recognize a particular three-manifold, having been given the three-manifold in one of its many possible triangulations. Applications of topology of three-manifolds range from questions of protein knotting and unknotting in DNA to the issue of the shape of space (the universe). In particular, the latter may very well come to an issue of recognizing the three-manifold that is our universe. Thus the classification and understanding of three-manifolds has far reaching applications and implications.

该研究项目的主要目标是进一步发展高效的三角剖分及其在三维流形研究和理解中的应用。0-和1-有效三角剖分导致了一些新的方法和结果的3-流形的三角剖分，决策问题，算法，计算复杂性，Heegaard分裂，和Dehn填充。我们建议进一步发展我们的理解0-和1-有效的三角剖分，并形成一个概念的g-有效的三角剖分（g 1）。我们的目标是建立有效三角剖分与三维流形上几何结构之间的明确联系，使用有效三角剖分来更好地理解三维流形的Heegaard分裂，并使用我们的方法将给定的三角剖分简化为有效三角剖分来实现三维流形同胚问题（三维流形的分类）的简化。 特别地，我们提出了判定3-流形是否为Haken流形、3-流形的JSJ分解和Haken流形识别的新算法。三维流形是在熟悉的三维空间上局部建模的数学对象。三维流形研究中的主要问题是分类问题，即把所有的三维流形不重复地列成一个完整的列表。本计画的主要目的是研究和了解三流形的分类。特别是，我们知道三流形可以被认为是以非常有组织的方式装配在一起的构建块的联合。例如，四面体可以用作构建块;在这种情况下，四面体的集合以及关于它们如何组合在一起的信息被称为三流形的三角测量。所有的三元流形都可以三角剖分。因此，解决分类问题的主要策略之一是找到识别特定三流形的方法，已经在其许多可能的三角剖分中给出了三流形。 三维流形拓扑学的应用范围从DNA中蛋白质的打结和解开到空间（宇宙）的形状。特别是，后者很可能会涉及到认识我们宇宙的三维流形的问题。因此，三维流形的分类和理解具有深远的应用和意义。