Efficient many-To-many point matching in one dimension

Justin Colannino, Mirela Damian, Ferran Hurtado, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane Souvaine, Godfried Toussaint

Research output: Contribution to journalArticle


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.

Original languageEnglish (US)
Pages (from-to)169-178
Number of pages10
JournalGraphs and Combinatorics
Issue numberSUPPL. 1
StatePublished - Jun 1 2007


ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this

Colannino, J., Damian, M., Hurtado, F., Langerman, S., Meijer, H., Ramaswami, S., Souvaine, D., & Toussaint, G. (2007). Efficient many-To-many point matching in one dimension. Graphs and Combinatorics, 23(SUPPL. 1), 169-178. https://doi.org/10.1007/s00373-007-0714-3