L. Boxer, R. Miller and A. Rau-Chaplin, "Some Scalable Parallel Algorithms for Geometric Problems,"


This paper considers a variety of geometric problems using the {\em coarse grained multicomputer} model: $p$ processors with $O(\frac{n}{p})$ local memory each, connected to some arbitrary interconnection network. It introduces efficient scalable parallel algorithms for several of classes of geometric problems including {\em rectangle finding problems} (all isonormal rectangles, all rectangles, all isonormal squares, all squares) and a variety of {\em lower envelope problems} (lower envelope of fixed degree polynomial functions, minimization of Hausdorff distances, and a variety of problems from dynamic computational geometry). All of the algorithms presented are {\em scalable} 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 scalability, 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.


If your library does not have a copy of this paper, please contact me, and I send you a paper version.