The complexity of low-distortion embeddings between point sets

ABSTRACT

We prove that it is NP-hard to approximate by a ratio better than 3 the minimum distortion of a bijection between two given finite three-dimensional sets of points.

REFERENCES

• 1: Tatsuya Akutsu , Kyotetsu Kanaya , Akira Ohyama , Asao Fujiyama, Point matching under non-uniform distortions, Discrete Applied Mathematics, v.127 n.1, p.5-21, April 2003 [doi>10.1016/S0166-218X(02)00282-2]
• 2: Helmut Alt , Kurt Mehlhorn , Hubert Wagener , Emo Welzl, Congruence, similarity and symmetries of geometric objects, Discrete & Computational Geometry, v.3 n.3, p.237-256, Jan., 1988 [doi>10.1007/BF02187910]
• 3: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 4: Sanjeev Arora, Satish Rao, Umesh Vazirani, "Expander flows and a sqrtlog n-approximation to sparsest cut," STOC 2004.
• 5: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 6: M. D. Atkinson, An optimal algorithm for geometrical congruence, Journal of Algorithms, v.8 n.2, p.159-172, June 1987 [doi>10.1016/0196-6774(87)90036-8]
• 7: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 8: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 9: A. Elad, and R. Kimmel "On bending invariant signatures for surfaces," IEEE Trans. on PAMI, 25, 10, pp. 1285--1295, 2003.
• 10: Uriel Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences, v.60 n.3, p.510-539, June 2000 [doi>10.1006/jcss.1999.1682]
• 11: James Haralambides, Fillia Makedon "Approximation Algorithms for the Bandwidth Minimization Problem for a Large Class of Trees" Theory Comput. Syst. 30(1), pp. 67--90, 1997.
• 12: Maurice Herlihy , Srikanta Tirthapura , Roger Wattenhofer, Competitive concurrent distributed queuing, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.127-133, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384001]
• 13: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 14: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 15: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a hilbert space. In Conference in modern analysis and probability, pages 189--206, 1984.
• 16: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007398]
• 17: Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
• 18: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 19: Christos H. Papadimitriou: The Euclidean Traveling Salesman Problem is NP-Complete. Theor. Comput. Sci. 4(3), pp. 237--244, 1977.
• 20: S. Vempala The Random Projection Method, SIAM, 2004.