Embedding tree metrics into low-dimensional Euclidean spaces

A. Gupta

doi:10.1007/s004540010020

Embedding tree metrics into low-dimensional Euclidean spaces

A. Gupta

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	105-116
Number of pages	12
Journal	Discrete and Computational Geometry
Volume	24
Issue number	1
DOIs	https://doi.org/10.1007/s004540010020
State	Published - Jul 2000

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s004540010020

Cite this

@article{75f0b4e804734324896d6b214fa7279b,

title = "Embedding tree metrics into low-dimensional Euclidean spaces",

abstract = "We consider embedding metrics induced by trees into Euclidean spaces with a restricted number of dimensions. We show that any weighted tree T with n vertices and L leaves can be embedded into d-dimensional Euclidean space with {\~O} (L1/(d-1)) distortion. Furthermore, 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} (n2/d) and almost matches the best known lower bound of Ω (L1/d).",

author = "A. Gupta",

year = "2000",

month = jul,

doi = "10.1007/s004540010020",

language = "English (US)",

volume = "24",

pages = "105--116",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Embedding tree metrics into low-dimensional Euclidean spaces

AU - Gupta, A.

PY - 2000/7

Y1 - 2000/7

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

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

UR - http://www.scopus.com/inward/record.url?scp=0034389097&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034389097&partnerID=8YFLogxK

U2 - 10.1007/s004540010020

DO - 10.1007/s004540010020

M3 - Article

AN - SCOPUS:0034389097

SN - 0179-5376

VL - 24

SP - 105

EP - 116

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Embedding tree metrics into low-dimensional Euclidean spaces

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this