Applied geometric algorithms on Boolean N-cube computers
Wei-Cheng Hsu, Xiaola Lin, Kuang-Hua Huang · 2003
Solutions for a class of geometric problems on N-cube parallel computers are studied. The geometric problems are the convex hull problem, the line intersection problem, and the nearest-neighbors problem. Existing results for the geometric problems and improved algorithms are discussed. For input to the algorithms, it is assumed that the N data points are evenly distributed on the M processors, where M=2/sup k/ for some integer k. The output is also represented in the distributive manner. The algorithms are based on the divide-and-conquer approach. Specifically, a problem is solved recursively by subdividing the input data into two subsets which are allocated on two subcubes until a primitive case is encountered and then combining (again recursively) the two partial results by using the communication links between the two subcubes.>