Low-Distortion Embeddings of Finite Metric Spaces
Piotr Indyk, Jiřı́ Matoušek · 2004
An n-point metric space (X, D) can be represented by an n × n table specifying the distances. Such tables arise in many diverse areas. For example, consider the following scenario in microbiology: X is a collection of bacterial strains, and for every two strains, one is given their dissimilarity (computed, say, by comparing their DNA). It is difficult to see any structure in a large table of numbers, and so we would like to represent a given metric space in a more comprehensible way. For example, it would be very nice if we could assign to each x ∈ X a point f(x) in the plane in such a way that D(x, y) equals the Euclidean distance of f(x) and f(y). Such a representation would allow us to see the structure of the metric space: tight clusters, isolated points, and so on. Another advantage would be that the metric would now be represented by only 2n real numbers, the coordinates of the n points in the plane, instead of ... numbers as before. Moreover, many quantities concern...