A divide-and-conquer algorithm for min-cost perfect matching in the plane

Given a set V of 2n points in the plane, the min-cost perfect matching problem is to pair up the points (into n pairs) so that the sum of the Euclidean distances between the paired points is minimized. We present an O(n^3/2log⁵ n)-time algorithm for computing a min-cost perfect matching in the plane, which is an improvement over the previous best algorithm of Vaidya [1989) by nearly a factor of n. Vaidya´s algorithm is an implementation of the algorithm of Edmonds (1965), which runs in n phases, and computes a matching with i edges at the end of the i-th phase. Vaidya shows that geometry can be exploited to implement a single phase in roughly O(n^3/2) time, thus obtaining an O(n^5/2log⁴ n)-time algorithm. We improve upon this in two major ways. First, we develop a variant of Edmonds algorithm that uses geometric divide-and-conquer, so that in the conquer step we need only O(√n) phases. Second, we show that a single phase can be implemented in O(n log⁵ n) time