Geometry helps in matching

ABSTRACT

A set of 2n points on the plane induces a complete weighted undirected graph as follows: The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under some metric. We study the problem of finding a minimum weight complete matching (MWCM) in such a graph. We give an &Ogr;(n23 (logn)4) algorithm for finding an MWCM in such a graph, for the L1 (manhattan), the L2 (euclidean), and the L∞ metrics. We also study the bipartite version of the problem, where half the points are painted with one color and the other half are painted with another color, and the restriction is that a point of one color may be matched only to a point of another color. We present an &Ogr;(n2.5 logn) algorithm for the bipartite version, for the L1, L2, and L∞, metrics. The running time for the bipartite version can be further improved to &Ogr;(n2 (logn)3) for the L1 and L∞ metrics.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: D. Avis, A survey of heuristics for the weighted matching problem, Networks, 13, 1983, pp. 475-493.
• 3: H. Edclsbrunner, L. J. Guibas, and I, Stolfi, Optimal point location in a monotone subdivision, Technical Report, DEC Systems Research Center, 1984.
• 4: I. Edmonds, Maximum matching and a polyhedron with 0, l-vertices, J. Res. Nat. Bur. Standards, 69B, 1965, 125- 130.
• 5: S Fortune, A sweepline algorithm for Voronoi diagrams, Proceedings of the second annual symposium on Computational geometry, p.313-322, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10549]
• 6: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 7: H.N. Gabow, and R. E. Tarjan, Faster scaling algorithms for network problems, Technical Report, 1987, Dept. of Comp. Sc., Princeton University.
• 8: Z. Galil, S. Micali, and H. N. Gabow, Priority queues with variable priority and an O (EViogV) algorithm for Rnding a maximal weighted matching in general graphs, Proc. 22nd Annual IEEE Syrup. Found. Cornp. Sc., 1982, pp.255-261.
• 9: M. Iri., M. Murota, and S. Matsui, Linear time heuristics for minimum-weight perfect matching on a plane with application to the plotter problem, Unpublished, 1980.
• 10: H. W. Kuhn, The Hungarian method for the assigment problem, Naval Res. Logistics Quart., 2, 1955, pp. 83-97.
• 11: E. LaMer, Combinatorial Optimization: Networks and Matroids, 1976, Holt Rinehart and Winston, New York, 1976.
• 12: D.T. Lee, and F. P. Preparata, Location of a point in a planar subdivision and its applications, SIAM J. Cornput., Vol. 6, 1977, pp. 594-606.
• 13: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 14: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 15: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 16: M. Sharir, Intersection and closest-pair problems for a set of planar discs, SIAM J. Comput., Vol. 14 (2), May 1985, pp. 448-468.
• 17: K. J. Supowit, and E. M. Reingold, Divide-and-Conquer heuristics for minimum weighted euclidean matching, SIAM J. Comput,, Vol 12. No. 1, 1983, pp. 118-144.
• 18: H.N. Oabow, and R. E. Tarjan, Faster scaling algorithms for graph matching, Tech. Report, Dept. of Computer Science, Princeton University. 1987.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Theory