An optimal parallel algorithm for triangulating a set of points in the plane (Q1100899)

This paper presents an optimal parallel algorithm for triangulating an arbitrary set of n points in the plane. The algorithm runs in O(log n) time using O(n) space and O(n) processors on a concurrent-read, exclusive-write parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is \(\Omega\) (log n) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into \(\sqrt{n}\) subproblems is employed.