Efficient Many-to-Many Point Matching in One Dimension.

Let S and T be two sets of points with total cardinality n. The minimum-cost many-to-mamny 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, which 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 aES to tET 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.

Main Author: Colannio, Justin.
Other Authors: Damian, Mirela., Hurtado, Ferran., Langerman, Stefan., Meijer, Henk., Ramaswami, Suneeta., Souvaine, Diane., Toussaint, Godfried.
Language: English
Published: 2007
Online Access: http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175668