Collaborative Research: Triangulating Manifolds of Low Dimension and Low Co-Dimension

空间中分散的数据点出现在许多情况下：科学数据的解释和分析;三维真实世界物体和场景的激光扫描;以及有限元法等科学计算技术的网格生成。 这些任务通常是最有效地执行的援助的几何结构称为三角形，特别是著名的德劳内三角。 虽然这些技术最明显的应用是在三维空间中，但人们通常希望分析更高维空间中的分散数据点。 例如，科学实验可能产生涉及许多变量的数据。这些数据被建模为高维空间中的点。 不幸的是，像Delaunay三角剖分这样的几何数据结构遭受“维数灾难”，并且可能非常大。 本研究课题探索Delaunay三角剖分或其他三角剖分在计算上易于处理的特殊情况，从而实现更有效的科学数据分析。离散数据插值、曲面重构、Delaunay三角剖分和网格生成等相关问题是计算几何的核心研究领域，在计算科学中具有重要影响。 这些领域的算法大多应用于三维空间。 本研究的三角剖分嵌入在高维环境空间，高达一千，在最容易处理的情况下：当输入点分布在流形上或附近的非常低的维度或非常低的余维。 一种称为星星展线的新技术构造了高维空间中低维流形的Delaunay样三角剖分。 该研究还试图表明，分散在低余维流形上的间隔良好的点具有较低的复杂性，因此易于处理。 这些结果的解释和参数化的科学数据集的应用。

Scattered data points in space arise in many contexts: the interpretation and analysis of scientific data; laser scanning of three-dimensional real-world objects and scenes; and the generation of meshes for scientific computing techniques like the finite element method. These tasks are often most effectively performed with the aid of geometric structures called triangulations, especially the well-known Delaunay triangulation. While the most apparent applications of these techniques are in three dimensions, people often want to analyze scattered data points in much higher-dimensional spaces. For instance, scientific experiments may produce data involving many variables. These data are modeled as points in a high-dimensional space. Unfortunately, geometric data structures such as Delaunay triangulations suffer ``the curse of dimensionality'' and can be prohibitively large. This project explores special cases in which Delaunay triangulations or other triangulations are computationally tractable, thereby enabling more effective scientific data analysis.The related problems of scattered data interpolation, surface reconstruction, Delaunay triangulation, and mesh generation form a central research area within computational geometry, and have a major impact in computational science. Algorithms in these areas have mostly been applied in dimension three. This research studies triangulations embedded in higher-dimensional ambient spaces, of up to one thousand, in the most tractable cases: when the input points are distributed on or near manifolds either of very low dimension or of very low co-dimension. A new technique called star splaying constructs Delaunay-like triangulations of low-dimensional manifolds in high-dimensional spaces. The research also seeks to show that well-spaced points scattered on manifolds of low co-dimension have low complexity, and are therefore tractable. These results have applications to the interpretation and parameterization of scientific data sets.