Faster Algorithms for Computing Distances between One-Dimensional Point Sets

Let S and T be two finite sets of points on the real line with |S| + |T| = n and |S| > |T|. We consider two distance measures between S and T that have applications in music information retrieval and computational biology: the surjection distance and the link distance. The former is called the restriction scaffold assignment problem in computational biology, and assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element s i of S to an element t j of T is |s i - t j |, i.e., the distance between s i and t j . In 2003 Ben-Dor, Karp, Schwikowski and Shamir [2] published an O(n log n) time algorithm for this problem. Here w