Geometry Helps in Matching

Abstract

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(n^{2.5} (\log n)^4 )$ algorithm is given for finding an MWCM in such a graph, for the $L_1 $ (manhattan ), the $L_2 $ (Euclidean), and the $L_\infty $ 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(n^{2.5} \log n)$ algorithm for the bipartite version, for the $L_1 $, $L_2$, and $L_\infty $ metrics, is presented. The running time for the bipartite version can be further improved to $O(n^2 (\log n)^3 )$ for the $L_1 $ and $L_\infty $ metrics.