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$ Jul 22 '17 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.