A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates
R. Sharathkumar · 2013
Let A, B ∈ [Δ]2, |A|=|B|=n, be point sets where each point has a positive integer coordinate bounded by Δ. For an arbitrary small constant δ > 0, we design an algorithm to compute a minimum-cost Euclidean bipartite matching of A,B in O(n{3/2+δlog (nΔ)) time; all previous exact algorithms for the Euclidean bipartite matching, even when the point sets have bounded integer coordinates take Ω(n2) time.