Algorithm design will be the key challenge of this project.
The sequential algorithm of Delaunay triangulation is non-trivial to begin with. Being a central topic in computational geometry, many algorithms rely on critical geometry primitives to implement and optimize. While the incremental insertion algorithm is easy to understand, it is inherently hard to parallelize.

A brief survey of related work gives us some insight into how parallelization might come into play here. First, it is possible to utilize a tradeoff between work-efficiency and scalability. Paper by Craig and Chen proposed one such solution, where by doing more “local” work for each vertex, it is possible to achieve almost linear speed up with multiprocessing. Also, a randomized incremental algorithm is proposed by Gu et al, where insertion of many new points are done concurrently, making it possible to parallelize each iteration of the algorithm.

General problems with parallel computation can be observed here as well. In terms of workload, since the insertion of each point is non-deterministic, in the sense that we don’t know how many “flips” it will trigger, it is important that we come up with some dynamic workload balancing mechanism. Locality is extremely important in the divide-and-conquer style algorithm, as well as in managing the frequent memory operations associated with keeping track of geometric properties such as vertices, edges, triangles, and etc.