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

空间中的散乱数据点出现在许多环境中：解释和分析科学数据；激光扫描真实世界的三维物体和场景；以及为科学计算技术(如有限元方法)生成网格。这些任务通常借助称为三角剖分的几何结构来最有效地执行，尤其是著名的Delaunay三角剖分。虽然这些技术最明显的应用是在三维空间中，但人们通常希望分析高维空间中的散乱数据点。例如，科学实验可能会产生涉及许多变量的数据。这些数据被建模为高维空间中的点。不幸的是，像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.