Uniqueness of ordinal embedding

Ordinal embedding refers to the following problem: all we know about an unknown set of points x1,…,xn∈Rd are ordinal constraints of the form ∥xi−xj∥<∥xk−xl∥; the task is to construct a realization y1,…,yn∈Rd 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.