This paper considers a variety of geometric problems based in description of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p)...
详细信息
This paper considers a variety of geometric problems based in description of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(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 interconnection network. We give an efficient scaleable parallel algorithm for computation of the lower envelope and use this algorithm to obtain 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 Intersection Problem for vertically convex planar polygons;and several problems in Dynamic Computational Geometry: in which we consider geometric questions for systems of moving objects. All of the algorithms presented are scaleable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition 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.
暂无评论