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.
