SCALEABLE PARALLEL ALGORITHMS FOR LOWER ENVELOPES WITH APPLICATIONS

This paper considers a variety of geometric problems based in descript ion of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Ome ga(n/p) local memory each (i.e., Omega(n/p) memory cells of Theta(log n) bits apiece), where the processors are connected to an arbitrary in terconnection network. We give an efficient scaleable parallel algorit hm for computation of the lower envelope and use this algorithm to obt ain efficient solutions for a variety of geometric problems, including the minimization of the Hausdorff distance between two finite sets on the real line when one is subject to translation; the Common Intersec tion Problem for vertically convex planar polygons; and several proble ms in Dynamic Computational Geometry: in which we consider geometric q uestions for systems of moving objects. All of the algorithms presente d are scaleable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addit ion to the practicality imparted by scaleability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations. (C) 1998 Academic Press.