Meshing in Fixed Dimension in near Optimal Work and Time Gary L Miller Computer Science Department Carnegie Mellon A finite element mesh or simply a mesh has has amazingly broad applicability. In its simplest form, the goal is to decompose a region into triangles/tetrahedra with good aspect ratio. The main use of a mesh is to represent succinctly functions in space and time. Thus meshes arise in areas such as scientific simulations, manufacturing, and graphics to mention only a few areas. On the other hand, robust and fast code has be elusive for what is a seemingly simple problem. One of the issues that has hampered quality code has been the lack of algorithms that works over a large class of problems. The lack of available code is so bad that many, if not most researchers doing complicated simulations have given up the hope of having available good meshes and have developed possibly suboptimal methods that do not rely on meshing. Good code seems to need algorithms with provable guarantees. Algorithms with quality, size, and run time guarantees have been much harder to find than expected. The case of 2D meshing has been a little easier. Over the last 17 years computer scientists have been in the forefront in designing algorithms with guarantees for the meshing problem. The work began with the quadtree meshing in 1990 and Ruppert's 1993 2D Delaunay Refinement algorithm. 3D versions of the 2D algorithms have been progressing much more slowly. In fact, some of the best progress has been done here a OSU. Prior to our work, no algorithms with subquadratic run-times were known in 3D. We have made progress on this front by developing a new meshing algorithm in any fixed dimension, Sparse Voronoi Refinement (SVR). The meshing problem in 3D, for example, takes as input a domain and a collection of features (points, edges, and faces) and decomposes the domain into tetrahedra. The algorithm has guarantees on size, quality and run time. SVR is a hybrid algorithm using the best features of the Octtree algorithm and Delaunay refinement. It has sequential-time/work bounds of O(n log n + m) for reasonable inputs of size n and outputs of size m. The input is in any fixed dimension with piecewise-linear constraining (PLC) features. The parallel time is O(log L/s log m)$ with the same work. SVR is straightforward enough that our 3D code demonstrates that it is both more robust and faster than other publicly available code. This represent joint work with Benoit Hudson and Todd Phillips