Generalized Delaunay mesh refinement: From scalar to parallel

The contribution of the current paper is three-fold. First, we generalize the existing sequential point placement strategies for guaranteed quality Delaunay refinement: instead of a specific position for a new point, we derive a selection disk inside the circumdisk of a poor quality triangle. We prove that any point placement algorithm that inserts a point inside the selection disk of a poor quality triangle will terminate and produce a size-optimal mesh. Second, we extend our theoretical foundation for the parallel Delaunay refinement. Our new parallel algorithm can be used in conjunction with any sequential point placement strategy that chooses a point within the selection disk. Third, we implemented our algorithm in C++ for shared memory architectures and present the experimental results. Our data show that even on workstations with a few cores, which are now in common use, our implementation is significantly faster the best sequential counterpart.