Abstract
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.
Recommended Citation
E. Shoemaker and R. Shoemaker. “Parallel greedy triangulation of a point set,” James Madison Undergraduate Research Journal, vol, 8, no. 1, pp. 24-30, 2021. [Online]. Available: http://commons.lib.jmu.edu/jmurj/ vol8/iss1/3.
