Uniqueness of Ordinal Embedding

Ordinal embedding refers to the following problem: all we know about an unknown set of points x_1,\ldots, x_n ∈\mathbbR^d are ordinal constraints of the form \|x_i - x_j\| < \|x_k - x_l\|; the task is to construct a realization y_1,\ldots, y_n ∈\mathbbR^d that preserves these ordinal constraints. It has been conjectured since the 1960ies that upon knowledge of all ordinal constraints a large but finite set of points can be approximately reconstructed up to a similarity transformation. The main result of our paper is a formal proof of this conjecture.