Triangulating a polygon in parallel
Michael T. Goodrich · Journal of Algorithms · 1989
In this paper we present an efficient parallel algorithm for polygon triangulation. The algorithm we present runs in O(log n) time using O(n) processors, which is optimal if the polygon is allowed to contain holes. This improves the previous parallel complexity bounds for this problem by a log n factor. If we are also given a trapezoidal decomposition of the polygon as input, then we can triangulate the polygon in O(log n) time using only O(nlog n) processors. This immediately implies that we can triangulate a monotone polygon in O(log n) time using O(nlog n) processors, which is optimal. All of our results are for the CREW PRAM computational model.