Embedding tree metrics into low dimensional Euclidean spaces

Anupam Gupta

Research output: Contribution to journalConference articlepeer-review

Abstract

We consider the question of embedding metrics induced by trees into Euclidean spaces with a restricted number of dimensions. We show that any weighted tree T with n(T) vertices and l(T) leaves can be embedded into d-dimensional Euclidean space with O(l(T)1/(d-1)) distortion. Further, we exhibit an embedding with almost the same distortion which can be computed efficiently. This distortion substantially improves the previous best upper bound of O(n(T)2/d) and almost matches the best known lower bound of Ω(l(T)1/d).

Original languageEnglish (US)
Pages (from-to)694-700
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

ASJC Scopus subject areas

  • Software

Cite this