AF: Small: The Fixed Point of the Restricted Delauay Triangulation Operator, with Applications to Manifold Reconstruction and Mesh Generation

研究人员将研究曲面重建和网格生成的相关问题。 表面重建是从仅仅表明对象形式的数据创建几何模型（通常是表面三角剖分）的问题。 最常见的是，表面重建算法的输入是由激光测距仪、立体摄影、医学图像、视频运动深度算法或甚至物理探头从真实世界对象采样的点组成的点云。 曲面重建在计算工程中用于执行物理模拟，在计算机图形学中用于获取真实世界的几何形状以放置在虚拟环境中，如视频游戏和电影特效，以及在测量中用于获取一块土地或一组建筑物的几何形状。网格生成是用复杂几何形状划分物理域的问题-例如，汽车发动机，人体的血管，或者飞机周围的空气--分解成小而简单的碎片，比如三角形或四面体。 网格生成中的一个重要问题是生成嵌入在三维空间中的表面网格，具体地说，是近似曲面的三角形网格。 曲面网格在计算机图形学、几何建模和可视化中是普遍存在的，这些领域的研究大多是在二维或三维空间中进行的。 有一种更高维度的表面重建类似物称为流形重建，通常用于科学数据分析。 科学和工程中的许多过程都以高维属性空间中的点的形式产生数据。 流形重构是发现约束点位于（近似）低维流形上的属性之间的关系的问题，本研究将流形重构和流形网格生成算法推广到嵌入d维环境空间的k维流形上，其中k的范围从2到10，d的范围从3到10，000甚至更大。 研究人员还将制作并公开发布用于三维流形重建的软件和用于从超大三维点云进行表面重建的核心外软件，以便科学家，工程师和几何建模人员可以使用数值模拟，计算机图形学和科学数据分析的方法。 这项工作将影响加州大学的教育和推广。伯克利分校通过培训研究生和本科生的研究和几何算法。

The investigators will study the related problems of surface reconstruction and mesh generation. Surface reconstruction is the problem of creating geometric models (usually surface triangulations) from data that merely suggests the form of an object. Most commonly, the input to a surface reconstruction algorithm is a point cloud consisting of points that have been sampled from a real-world object by laser range finders, stereo photography, medical images, video depth-from-motion algorithms, or even physical probes. Surface reconstruction is used in computational engineering to perform physical simulations, in computer graphics to acquire real-world geometry to place in virtual environments such as videogames and movie special effects, and in surveying to acquire the geometry of a plot of land or a collection of buildings.Mesh generation is the problem of dividing a physical domain with a complicated geometry--say, an automobile engine, a human's blood vessels, or the air around an airplane--into small, simple pieces such as triangles or tetrahedra. An important problem within mesh generation is the generation of surface meshes embedded in three dimensions--specifically, triangle meshes that approximate curved surfaces. Surface meshes are ubiquitous in computer graphics, geometric modeling, and visualization.Most prior work on these topics has been set in 2- or 3-dimensional space. There is a higher-dimensional analog of surface reconstruction called manifold reconstruction, commonly used for scientific data analysis. Many processes in science and engineering produce data in the form of points in a high-dimensional space of attributes. Manifold reconstruction is the problem of discovering relationships between the attributes that restrict the points to lie (approximately) on a low-dimensional manifold.This research will generalize algorithms for manifold reconstruction and manifold mesh generation to operate on k-dimensional manifolds embedded in a d-dimensional ambient space, where k ranges from 2 to perhaps 10 and d ranges from 3 to 10,000 or even greater. The investigators will also produce and publicly release software for manifold reconstruction in d dimensions and out-of-core software for surface reconstruction from extremely large three-dimensional point clouds so that scientists, engineers, and geometric modelers can use the methods for numerical simulation, computer graphics, and scientific data analysis. The work will impact education and outreach at U.C. Berkeley by training graduate and undergraduate students in research and geometric algorithms.