On the parallel-decomposability of geometric problems

There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n ^1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen >p. The goal we seek is to achieve, when solving a problem of sizen >p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen >p as when solving a problem of sizep.The research of M. J. Atallah was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Jyh-Jong Tsay's research was partially supported by the Office of Naval Research under Contract N00014-84-K-0502, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, and the National Science Foundation under Grant DCR-8451393.