Scalable parallel algorithms for geometric pattern recognition

This paper considers a variety of geometric pattern recognition problems 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. It introduces efficient scalable para llel algorithms for a number of geometric problems including the rectangle finding problem, the maximal equally spaced collinear points problem, and t he point set pattern matching problem. All of the algorithms presented are scalable in that they are applicable and efficient over a very wide range o f ratios of problem size to number of processors. In addition to the practi cality imparted by scalability, these algorithms are easy to implement in t hat all required communications can be achieved by a small number of calls to standard global routing operations. (C) 1999 Academic Press.