Patent ID: 6088511
Filing Date: 2000-07-11
Classification: G06F

Abstract:
A parallel two-dimensional triangulation method comprising:executing a recursive main program by subdividing processors in a parallel machine into teams, executing the main program in a control parallel manner such that each team executes a call to the main program in parallel;wherein the main program includes the following steps:taking as input a data structure representing a collection of points in two-dimensional space;in a data parallel operation across each of the processors in the team, finding internal points in the collection of points;when no internal points remain, returning a collection of triangles:when internal points remain, performing the following steps:a) computing a median of the collection of points;b) projecting the collection of points onto a parabola;c) finding a lower convex hull of the projected points by distributing the points among the processors in the team and executing a parallel convex hull routine within the team, including subdividing the processors in the team into sub-teams, with one sub-team per parallel function call;d) creating two borders for the collection of points; ande) invoking the main program on two new collections of points defined by the two borders.