Efficient Many-To-Many Point Matching in One Dimension

Appears in Graphs and Combinatorics, vol. 23 (2007), supplement, Computational Geometry and Graph Theory. The Akiyama-Chvatal Festschrift. The original publication is available at www.springerlink.com. Abstract. Let S and T be two sets of points with total cardinality n. The minimum-cost many-to-many matching problem matches each point in S to at least one point in T and each point in T to at least one point in S, such that sum of the matching costs is minimized. Here we examine the special case where both S and T lie on the line and the cost of matching s ∈ S to t ∈ T is equal to the distance between s and t. In this context, we provide an algorithm that determines a minimum-cost many-to-many matching in O(n log n) time, improving the previous best time complexity of O(n 2) for the same problem. 1