chapter  8
21 Pages

8: Low-distortion embeddings of finite metric spaces

WithPiotr Indyk, Jiří Matoušek, Anastasios Sidiropoulos

An n-point metric space (X, D) can be represented by an n × n $ n \times 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.