Abstract:
A new meshing algorithm will be presented for meshing with boundaries in any fixed dimension, Sparse Voronoi Refinement (SVR). The meshing problem in 3D, for example, takes as input a a domain and a collection of features(points, edges, and faces) and decomposes the domain into tetrahedra.
There are four important properties that a meshing algorithm should have: 1) The tetrahedra should have good aspect ratio, no small angles. 2) The mesh should conform to the features. 3) The size should be competitive to an optimal-size mesh. 4) The algorithm should be work and time competitive with a optimal algorithm.
SVR is the first algorithm known to have have all four properties even in 3D for a reasonable assumption about the input.
Over the last 17 years computer scientists have been in the forefront in designing algorithms with guarantees for all four conditions, beginning with the pioneering work of Bern, Eppstein, and Gilbert on quadtree meshing in 1990. Their algorithm has all 4 guarantees for 2D points where the work is O(n log L/s + m). Here L/s is the ratio of the size of the domain over the smallest input feature. In 1993 Ruppert proposed a method called Delaunay Refinement which included guarantees for the first three conditions in 2D.
The 3D octtree algorithms starts by insuring 1) always and finishes by insuring 2), while Delaunay Refinement algorithms first insure 2) then refine until 1) is satisfied. SVR can be viewed as a compromise by alternately insuring 1) and then 2). SVR has sequential-time/work bounds of O(n log L/s + m) for inputs in any fixed dimension with piecewise-linear constraining (PLC) features. The parallel time is O(log L/s log m)$ on an EREW PRAM, with the same work. SVR is straightforward enough that it is likely to be extremely fast in practice.
This represent joint work with Benoit Hudson and Todd Phillips