A Faster Algorithm for Computing the Link Distance Between Two Point Sets on the Real Line
Justin Colannino, Godfried Toussaint · 2005
Let S and T be point sets with |S| # |T | and total cardinality n. A linking between S and T is a matching, L, between the sets where every element of S and T is matched to at least one element of the other set. The link distance is defined as the minimum-cost linking. In this note we consider a special case of the link distance where both point sets lie on the real line and the cost of matching two points is the distance between them in the L 1 metric. An O(n ) algorithm for this problem is presented, improving the previous best known complexity of O(n ).