SOLVING GEOMETRIC PROXIMITY PROBLEMS ON MESH-CONNECTED COMPUTERS.

The authors present parallel MCC algorithms for solving the all-points nearest-neighbor and closest-pair problems for a set of n planar points represented by their Cartesian coordinates. The algorithms execute on a ROOT n multiplied by ROOT n MCC and have O( ROOT n) time performance. They also present an algorithm for finding the closest pair between two sets. Given two sets with number of points m and n, respectively, and N equals m plus n, the algorithm is performed on an N**2 **/ **3 multiplied by N**2 **/ **3 MCC, and the time complexity is O(n**2 **/ **3 ). An O(n**2 **/ **1**0**0 log n)-time algorithm is given for constructing the Euclidean minimum spanning tree on a planar points using an n**2 **/ **3 multiplied by n**2 **/ **3 MCC. The best known sequencing algorithms for these problems have an optimal O(n log n) time complexity.

IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Ma

SOLVING GEOMETRIC PROXIMITY PROBLEMS ON MESH-CONNECTED COMPUTERS. Conference Paper