A greedy triangulation algorithm takes a set of points in the plane and returns a triangulation of the point set. The triangulation is built by adding the smallest line segment between points that does not intersect any line previously in the triangulation. The greedy triangulation is inexpensive computationally and gives an approximation of the minimum-weight triangulation problem, an NP-hard problem, which is computationally expensive. We present serial and parallel implementations of the greedy triangulation using the following approach: once a line is added to the triangulation, all intersecting lines are removed from consideration. This process is repeated until a triangulation is obtained. We present and analyze experimental wall-time data for the serial and parallel implementations. We show that the parallel version has strong and weak scaling properties, and that this algorithm benefits greatly from parallelism.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.