AF: Medium: Theory and Practice of Optimal Meshing

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Meshing has been a cornerstone for simulations using the finite element method. But more recently it has had applications wherever one needs to define a function over a domain, such as, graphics, computer aided design, robotics, and even machine learning. Algorithms will be designed to efficiently work in any fixed dimension with guarantees on output size and quality. At present, no theory exists to formulate and produce optimal meshes in the presence of small input angles even for the 2D case. The research will find efficient algorithms 2D and higher dimension that generate optimal size Delaunay triangulations using only simplices with no angles approaching 180 degrees. Machine learning applications need a meshing algorithm that runs in polynomial time for meshing n points in log n dimensions. Historically, meshing algorithms return a set of space-filling simplices. Even good aspect ratio simplices have too small a volume and return a mesh that is of super polynomial size. Thus, new algorithms will be developed that handle atomic objects that are have much larger volume than simplices. The results from this project are eminently practical and have broad impact on the Sciences, Engineering, Manufacturing, and Machine Learning. In particular, meshing is an enabling technology for designing efficient windmills and cars, and simulations of earth quakes and medial devices. One goal is to incorporated techniques from this research into our first generation 3D code that we made available on the web. In addition, this material will be incorporated into classes taught at CMU, lectures, and papers presented at conferences.