Some Scalable Parallel Algorithms for Geometric Problems.

L. Boxer, R. Miller, and A. Rau-Chaplin

Abstract: This paper considers a variety of geometric problems using the 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 a number of geometric problems including the rectangle finding problem, the iso-oriented line intersection counting problem, a variety of lower envelope problems, the minimal circle-covering problem, the maximal equally-spaced collinear points problem, and the point set pattern matching problem. All of the algorithms presented are 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.