Sorting and Searching
The program builds a k-d tree using random coordinate points, then searches the k-d tree for points that are proximate to each point in the tree.
The build phase is single threaded, but the search phase is multi-threaded using the OpenMP task directive.
The points that are sorted into the tree are defined using a random number gener ator to generate either 3D (x,y,z) or 4D (x,y,z,w) points that are stored one large 2 D array, xyzw. In order to build the k-d tree, four index arrays xi, yi, zi and wi are created then heap-sorted using the x, y, z and w coordinate data from the xy zw array. The k-d tree is a balanced tree, and is built in O[n*log(n)] time.
Once the k-d tree is built, the k-d tree is walked to visit each point, and that point is used as a query point to search the k-d tree for all other points that lie within a specific radius of that query point. The default value for that radius is one-tenth the range of the random numbers. The total number of points found by using each point successively as a query point, as well as the total execution time, are reported. Note that the walking and searching of the k-d tree imply two recursive traversals of the k-d tree.
The program returns the number of points found to meet the input criteria.