Some Scalable Parallel Algorithms for Geometric Problems. 

L. Boxer, R. Miller, and A. RauChaplin 

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 isooriented line intersection counting problem, a variety of lower envelope problems, the minimal circlecovering problem, the maximal equallyspaced 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. 

paper.pdf 
paper.ps 

