The embedding problem of classical distance geometry is the problem of determining when a specified nxn matrix can be realized as the pairwise distances between n points in Euclidean space. Constructive solutions of the embedding problem in the 1930s inspired classical multidimensional scaling, a psychometric technique for visualizing fallible dissimilarity data. After providing some relevant background, I will discuss several ways in which facts about the geometry of Euclidean distance matrices have informed recent research in multidimensional scaling (MDS).

First, I will discuss the problem of choosing a good initial configuration from which to begin numerical optimization of the popular raw stress and sstress criteria for metric MDS. Most commercial algorithms use the classical solution, which can be computed explicitly but whose interpoint distances tend to be too small. One can do better by (1) dilating the classical solution, or by (2) solving a simple approximation of the raw sstress problem.

Second, I will discuss extensions of classical MDS, from the case of a single fixed dissimilarity matrix to closed convex sets of dissimilarity matrices. Important special cases include bound constraints, which leads to new algorithms for distance matrix completion (with applications to molecular conformation), and order constraints, which leads to new algorithms for nonmetric MDS.

Third, I will discuss new results on spherical distance matrices that may be connected to a phenomenon known as the horseshoe effect, which arises when MDS is used for seriation.