NESTED PARALLEL 2D DELAUNAY TRIANGULATION METHOD

A nested parallel implementation of 2D triangulation method recursively sub-divides processors of a parallel computer into asynchronous processor teams. Each of the teams uses data parallel operations to compute a partitioning of the collection of points distributed to it. When each team has a single processor as a result of the recursive partitioning steps, the processors switch to a serial version of the 2D triangulation method. The nested parallel implementation has two levels of recursion: 1) one to partition a collection of points into two new sets; and 2) a second layer nested in the first to compute convex hulls used to form a border around the two new sets of points. In each layer of recursion the implementation sub-divides processors into teams and assigns a control parallel function to each team. Within each team, the processors perform data parallel operations on the collection of points distributed to the processors in the team.