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

Overview

Identity

Additional Document Info

View All

Overview

abstract

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.