Triangulated Spaces: Algorithms and Combinatorics

9321799这个项目致力于开发三角剖分空间(多面体、点集)的高效算法，为三角化空间设计高效的拓扑算法，并理解三角化空间的组合方面。三角空间在许多领域都有广泛的应用，也有着直接的理论意义。首先将重点放在更高维度的多面体三角剖分和点集三角剖分的算法上。有限元方法应用三角剖分来分解区域，而计算机图形学和实体建模则使用它们来表示具有较简单组件的对象并有效地操纵它们。接下来，我们将集中研究三角空间的拓扑算法来解决两个问题：(I)确定任意维单纯形复形的同调群；(Ii)判断单纯形复形上给定的两个圈是否可以连续地相互变形。计算拓扑学是一个新兴的领域，它研究拓扑问题的计算方面。这些构造性的方法将算法理论注入到拓扑学中，使其在实际应用中更加有用。为了理解三角空间，人们需要更多地了解它们的组合行为。项目后半部分的重点将集中在这样的组合问题上，如计算一组简单中的交叉点的数量，以及计算一个点集的组合不同三角剖分的数量。

9321799 Dey This project seeks to develop efficient algorithms for triangulating spaces (polytopes, point sets), to design efficient topological algorithms for triangulated spaces, and to understand the combinatorial aspects of triangulated spaces. Triangulated spaces appear in many applications, and have immediate theoretical interest as well. The focus will first be on algorithms for polytope triangulations and point set triangulations in higher dimensions. Finite element methods apply triangulations to decompose the domains, while computer graphics and solid modeling use them to represent objects with simpler components and to manipulate them efficiently. Next, the investigation will concentrate on topological algorithms with triangulated spaces for two problems: (i) determining the homology groups of simplicial complexes in arbitrary dimensions, (ii) detecting if two given cycles on a simplicial complex can be continuously deformed to one another. Computational topology, an emerging field, examines the computational aspects of topological problems. The constructive approaches would inject algorithmic theories into topology, making it more useful in practical applications. To understand triangulated spaces, one needs to know more about their combinatorial behavior. The focus in the latter half of the project will be on such combinatorial questions as counting the number of crossings in a set of simplices and counting the number of combinatorially different triangulations for a point set.