If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their vertex set?

For instance, an equilateral triangle has this property, as (1,0,0), (0,1,0), and (0,0,1) form an equilateral triangle and are corners of the unit cube.

This is related to some larger work on L1 and L2 embeddings into a box, on which I have some passing familiarity with the literature (Menger's theorem, Schoenberg, etc.).


Solved. The answer is to square the edge lengths and test if the result is L1 embeddable. Details to come at some unspecified future time.

  • 2
    $\begingroup$ Testing whether a metric space embeds into L1 is NP-hard. $\endgroup$ – Yury Jun 6 '17 at 14:56
  • $\begingroup$ Can you test approximate L1 embedding? (That is, testing whether a distortion of a metric space is L1 embeddable, if I am allowed to distort each distance by between 1-eps and 1+eps) $\endgroup$ – Timothy Chu Jul 22 '17 at 20:50

Your Answer

