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

doi:10.1007/s00373-007-0714-3

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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 ²) for the same problem.

Original language	English (US)
Pages (from-to)	169-178
Number of pages	10
Journal	Graphs and Combinatorics
Volume	23
Issue number	SUPPL. 1
DOIs	https://doi.org/10.1007/s00373-007-0714-3
State	Published - Jun 2007

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-007-0714-3

Cite this

@article{044924b5cb1742c98cc81323e0e3f184,

title = "Efficient many-To-many point matching in one dimension",

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.",

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

year = "2007",

month = jun,

doi = "10.1007/s00373-007-0714-3",

language = "English (US)",

volume = "23",

pages = "169--178",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "SUPPL. 1",

}

TY - JOUR

T1 - Efficient many-To-many point matching in one dimension

AU - Colannino, Justin

AU - Damian, Mirela

AU - Hurtado, Ferran

AU - Langerman, Stefan

AU - Meijer, Henk

AU - Ramaswami, Suneeta

AU - Souvaine, Diane

AU - Toussaint, Godfried

PY - 2007/6

Y1 - 2007/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34547354365&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34547354365&partnerID=8YFLogxK

U2 - 10.1007/s00373-007-0714-3

DO - 10.1007/s00373-007-0714-3

M3 - Article

AN - SCOPUS:34547354365

SN - 0911-0119

VL - 23

SP - 169

EP - 178

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - SUPPL. 1

ER -

Efficient many-To-many point matching in one dimension

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this