An E P algorithm for computing a minimum weight perfect matching for a set of points on the plane

Given a graph induced by an even number of points on the plane, the minimum weight matching problem calls for finding a pairing of all the points such that the sum of the distances between the paired points is the smallest possible. In this paper, we propose a parallel algorithm for this problem. The algorithm is designed for the EREW PRAM model of parallel computation with p processors. For points on the Euclidean and manhattan planes, the algorithm executes in O((n^2.5log⁴n)/p) time, where p ⩽ n^0.5. The algorithm provides an optimal speedup with respect to the fastest existing sequential algorithm.