Given two point sets S and T, a limited-capacity many-to-many matching (LCMM) between S and T matches each point p in S (resp. T) to at least 1 and at most Cap(p) points in T (resp. S), where the function Cap:S\cup T-> Z>0 denotes the capacity of p. In this paper, we present the first linear time algorithm for finding a minimum-cost one dimensional LCMM (OLCMM) between S and T, where S and T lie on the line and the cost of matching p in S to q in T equals the l_2 distance between p,q. Our algorithm improves the previous best known quadratic time algorithm.
翻译:给两个点设置S和T, S和T之间的能力有限,多到多匹配(LCMM),与S(resp.T)中的每个点匹配到T(resp.S)中的至少一个点,最多是Cap(p)点(p)点(resp.S),函数Cap:S\cup T- > ⁇ 0表示p的能力。 在本文件中,我们提出了在S和T之间找到一个最低成本的一维LCM(OLCMM)的第一次线性时间算法,S和T处于线上,而S到Q的匹配成本等于p,q。我们的算法改进了以前最已知的四边时间算法。