Mesh generation is a key step in graphics rendering and in using the finite-element method to solve partial differential equations. The goal of mesh generation is to discretize the domain of interest using polygonal elements such as triangles (in 2-D) or tetrahedra (in 3-D).

One popular mesh generation algorithm is Delaunay mesh generation,
which produces meshes with certain quality guarantees that are
important for problems in which the geometry of the problem changes
with time. Delaunay mesh generation works by iterative refinement of
a coarse initial mesh. The sequential algorithm repeatedly looks for
a ``bad" mesh element that does not satisfy the quality constraints,
computes a neighborhood of that element called its *cavity*, and
replaces the elements in that cavity with new elements, some of
which may not satisfy the quality guarantees themselves. It can be
shown that the algorithm always terminates and produces a guaranteed
quality mesh, regardless of the order in which bad elements are
processed.

Delaunay mesh generation can be parallelized in a natural way because elements that are far away in the mesh do not interfere with each other as they are being processed. We present experimental results showing that in practice, there is indeed a lot of parallelism that is exposed in this way. However, exploiting this parallelism in practice can be complicated. Compile-time analysis and parallelization are infeasible because of the input-dependent nature of the algorithm. One alternative is optimistic parallelization. We show how logical transactions can be identified in a natural way in this code, argue that current transactional memory implementations are inadequate for this application, and suggest an alternative conception of transactional memory that addresses these problems.