Bipartite graph matching for points on a line or a circle |
| |
| Affiliation: | 1. Department of Biomedical Engineering, University of Michigan, Ann Arbor, MI 48109, USA;3. Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA;4. Department of Mechanical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA;1. Shanghai Key Laboratory of Atmospheric Particle Pollution and Prevention, Department of Environmental Science & Engineering, Fudan University, Shanghai 200433, People''s Republic of China;2. Shanghai Institute of Pollution Control and Ecological Security, Shanghai 200092, People''s Republic of China |
| |
| Abstract: | Given two sets of M points on a line or on a circle, a minimal matching between them is found in O(M log M) time. The circular case, where the distance between two points is the length of the shortest arc connecting them, is shown to have the same complexity as the simpler linear case. Finding the shift of one of the sets, linear or circular, that minimizes the cost of matching is also discussed. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
