<p>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.</p>

CC BY-SA 3.0
2017-06-06T14:56:42.877Z
Testing whether a metric space embeds into L1 is NP-hard.
Yury
CC BY-SA 3.0
2017-07-22T20:50:05.877Z
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)
Timothy Chu
CC BY-SA 3.0
2017-06-03T09:08:53.477Z
2017-06-03T09:08:53.477Z
Timothy Chu
<p>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?</p>

<p>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.</p>

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

<computational-geometry><convex-geometry><embeddings>
Embedding points in Euclidean space into a box
Timothy Chu
# Embedding points in Euclidean space into a box

(Asked by: username_0 on 2017-05-27)

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

**Tags:** computational-geometry, convex-geometry, embeddings

---

## 1 answers

### Answer by username_0 on 2017-06-03. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_1**: Testing whether a metric space embeds into L1 is NP-hard.  
> **username_0**: 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)  

---

