A near linear time constant factor approximation for Euclidean bichromatic matching (cost)

ABSTRACT

We give an Nlog^O(1) N-time randomized O(1)-approximation algorithm for computing the cost of minimum bichromatic matching between two planar point-sets of size N.

REFERENCES

• 1: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.39-50, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220284]
• 2: Kasturi R. Varadarajan , Pankaj K. Agarwal, Approximation algorithms for bipartite and non-bipartite matching in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.805-814, January 17-19, 1999, Baltimore, Maryland, United States
• 3: Pankaj Agarwal , Kasturi Varadarajan, A near-linear constant-factor approximation for euclidean bipartite matching?, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997856]
• 4: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 5: {CGKR05} S. Cabello, P. Giannopoulos, C. Knauer, and G. Rote. Matching point sets with respect to the earth mover's distance. Proceedings of the European Symposium on Algorithms, pages 520--531, 2005.
• 6: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 7: {IT03} P. Indyk and N. Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
• 8: {KV05} O. Klein and R. C. Veltkamp. Approximation algorithms for computing the earth mover's distance under transformations. Proceedings of the 16th Annual Symposium on Algorithms and Computation, 2005.
• 9: {Law76} E. Lawler. Combinatorial optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
• 10: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 11: Assaf Naor , Gideon Schechtman, Planar Earthmover is not in L_1, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.655-666, October 21-24, 2006 [doi>10.1109/FOCS.2006.60]
• 12: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000 [doi>10.1023/A:1026543900054]
• 13: P. M. Vaidya, Geometry helps in matching, SIAM Journal on Computing, v.18 n.6, p.1201-1225, Dec. 1989 [doi>10.1137/0218080]