AF: Medium: Theory and Practice of Optimal Meshing

网格划分一直是使用有限元方法进行模拟的基石。但最近，它有了一些需要在某个领域定义函数的应用，如图形、计算机辅助设计、机器人学，甚至机器学习。算法将被设计成在任何固定的维度下有效地工作，并保证输出尺寸和质量。目前，即使对于2D情况，也不存在在存在小输入角的情况下建立和产生最优网格的理论。研究将发现高效的算法2D和高维，仅使用不接近180度的任何角度的简化来生成最佳尺寸的Delaunay三角剖分。机器学习应用需要一个网格划分算法，该算法以多项式时间运行来划分对数n维中的n个点。历史上，网格划分算法返回一组填充空间的简化。即使是好的纵横比简图，体积也太小，返回的网格是超多项式大小的。因此，将开发新的算法来处理体积比简单大得多的原子对象。该项目的结果非常实用，并对科学、工程、制造和机器学习产生影响。特别是，啮合是一项使设计高效风车和汽车、模拟地震和医疗设备的技术成为可能。一个目标是将这项研究的技术整合到我们在网络上提供的第一代3D代码中。此外，这些材料将被纳入到CMU的课堂、讲座和在会议上提交的论文中。

Meshing has been a cornerstone for simulations using the finiteelement method. But more recently it has had applications whereverone needs to define a function over a domain, such as, graphics,computer aided design, robotics, and even machine learning. Algorithmswill be designed to efficiently work in any fixed dimension withguarantees on output size and quality.At present, no theory exists to formulate and produce optimal meshesin the presence of small input angles even for the 2D case. Theresearch will find efficient algorithms 2D and higher dimension thatgenerate optimal size Delaunay triangulations using only simpliceswith no angles approaching 180 degrees.Machine learning applications need a meshing algorithm that runs inpolynomial time for meshing n points in log n dimensions.Historically, meshing algorithms return a set of space-fillingsimplices. Even good aspect ratio simplices have too small a volumeand return a mesh that is of super polynomial size. Thus, newalgorithms will be developed that handle atomic objects that are havemuch larger volume than simplices.The results from this project are eminently practical and have broadimpact on the Sciences, Engineering, Manufacturing, and MachineLearning. In particular, meshing is an enabling technology fordesigning efficient windmills and cars, and simulations of earthquakes and medial devices. One goal is to incorporated techniquesfrom this research into our first generation 3D code that we madeavailable on the web. In addition, this material will be incorporatedinto classes taught at CMU, lectures, and papers presented atconferences.