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

合作研究：低维和低余维三角流形

• 批准号: 0635381
• 负责人: Jonathan Shewchuk
• 金额: $ 28万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-03-01 至 2011-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635381&HistoricalAwards=false
• 关键词: Collaborative; Research; Triangulating; Manifolds; Low

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.

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