6
$\begingroup$

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.).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Testing whether a metric space embeds into L1 is NP-hard. $\endgroup$
    – Yury
    Jun 6, 2017 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, 2017 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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