Embedding tree metrics into low-dimensional Euclidean spaces (Q1577550): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004540010020 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2043174865 / rank | |||
Normal rank |
Latest revision as of 00:33, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Embedding tree metrics into low-dimensional Euclidean spaces |
scientific article |
Statements
Embedding tree metrics into low-dimensional Euclidean spaces (English)
0 references
24 August 2000
0 references
The article under review is a valuable contribution in a common field of geometry, graph, complexity and probability theory. It is concerned with embedding metrics induced by trees into Euclidean spaces (of dimension \(d\), e.g., \(\ell^d_p\); or spheres). Given metric spaces \(M= (X,\rho)\), \(M'= (Y,\mu)\), the contraction \(D_c(f)\) of a map \(f: X\to Y\) is the supremum over \(\rho(x, y)\) divided by \(\mu(f(x), f(y))\). The distortion is defined by \(D(f)= D_c(f)\cdot D_e(f)\), where the expansion \(D_c(f)\) is the supremum over the reverse relation. Herewith, the distortion of an embedding \(f\) is the maximum factor by which any distance is changed by the embedding. The main results consist in improving the efficiency of computing \(D(f)\). By an analysis of embedding, the author shows that any weighted tree with \(n\) vertices and \(L\) leaves can be embedded with \(D(f)= \widetilde O(L^{1/(d-1)})\). Then, he studies the embedding of stars proving distortions \(\Omega(L^{1/d})\), \(O(L^{1/d})\) in the unweighted and weighted case, respectively. By applying random projection arguments (under Gaussian distribution) and Lovász local lemma, the research finally arrives at \(D(f) =\widetilde O(n^{1/d})\) for a special tree class. Appendices on spherical codes and constructive examples conclude the article. In future, a number of applications may be expected in coding theory, geometrical data analysis, graph drawing or biomathematics.
0 references
embedding metrics
0 references