Scalable parallel geometric algorithms for coarse grained multicomputers

摘要: Whereas most of the literature assumes that number processors p is a function problem size n, in scalable algorithms becomes parameter time complexity. This more realistic modelisation real parallel machines and yields optimal algorithms, for case n H p, where depending on architecture interconnexion network. In this paper we present geometric problems, namely lower envelope line segments, 2D-nearest neighbour, 3D-maxima, 2D-weighted dominance counting area union rectangles, 2D-convex hull. The main idea these to decompose subproblems 0(F(n;p) + f(p)), with f(p) 2 F(n;p) , which can be solved independently using sequential algorithms. For each spatial decomposition scheme based some observations. schemes have common they computed by globally sorting entire data set at twice. redundancy duplicates elements per processor does not increase asymptotic complexity ranges presented paper, from p2. do depend specific architecture,they are easy implement practice efficient as experiments show.