Geometry Helps in Matching

A set of $2n$ points on the plane induces a complete weighted undirected graph as follows. The points are the vertices of the graph, and the weight of an edge between any two points is the distance between the points under some metric. The problem of finding a minimum weight complete matching (MWCM) in such a graph is studied. An O(n2.5 (log n)⁴ ) algorithm is given for finding an MWCM in such a graph, for the L₁ (manhattan ), the L₂ (Euclidean), and the L_∞ metrics. The bipartite version of the problem is also studied, where half the points are painted with one color and the other half with another color, and the restriction is that a point of one color may be matched only to a point of another color. An O(n2.5 log n) algorithm for the bipartite version, for the L₁, L₂, and L_∞ metrics, is presented. The running time for the bipartite version can be further improved to O(n² (log n)³ ) for the L₁ and L_∞ metrics.