How can a set of max 5 points be found to encompass a 4D hypercube?

[jacobrhcp]

Hi!

I stumbled upon something I need to implement my problem in a computer. Because I think its actually fun to puzzle on, I thought it might be nice to post it here. The problem is this:

If you have a 4D hypercube, (a_1,b_1)\times(a_2,b_2)\times(a_3,b_3)\times(a_4,b_4), what is an easy algorithm to find a set of max 4+1 points that encompasses the hypercube?

For 2D, ie (a_1,b_1)\times(a_2,b_2), its easier, as you can find 2+1 points by taking the points (a_1-|a_1-b_1|,a_2), (b_1+|a_1-b_1|,a_2), and the point that is the intersection of the lines defined by the points (a_1-|a_1-b_1|,a_2), (a_1, b_2) and (b_1+|a_1-b_1|,c), (b_1,b_2), respectively (if you draw this it becomes clear immediately =P). If you expand this procedure to 4D, things get complicated fast. Is there a simple way to find a set of max 5 points that encompasses my hypercube?

Edit: I noticed I say 'cube', but as a_i, b_i \in ℝ, it doesn't need to be a cube at all of course.

 

[theorem4.5.9]

I am trying to see what you are asking, but I have some questions.

By $(a_1, b_1)\times (a_2,b_2)$ do you mean the parallelogram induced by these two vectors, with one coordinate being the origin, the other as $(a_1+a_2, b_1 +b_2)$?

By encompass (in the 2-d example) are you trying to find a triangle which simply covers the parallelogram?

I do not know what $(a_1,b_1) \times (a_2, b_2) \times (a_3, b_3) \times (a_4, b_4)$ means if $a_i, b_i \in \mathbb{R}$

 

[Mark44]

I am trying to see what you are asking, but I have some questions.

By $(a_1, b_1)\times (a_2,b_2)$ do you mean the parallelogram induced by these two vectors, with one coordinate being the origin, the other as $(a_1+a_2, b_1 +b_2)$?

I believe the OP means the rectangle {(x, y) | a₁ < x₁ < a₂, b₁ < x₂ < b₂}

By encompass (in the 2-d example) are you trying to find a triangle which simply covers the parallelogram?

I do not know what $(a_1,b_1) \times (a_2, b_2) \times (a_3, b_3) \times (a_4, b_4)$ means if $a_i, b_i \in \mathbb{R}$

I believe it means the 4D box whose description is similar to the rectangle I described above (but in R⁴).

 

[theorem4.5.9]

Of course that's what he means, thanks! Though just one minor correction, $\left\{ (x,y) : a_1 \leq x \leq b_1 , a_2 \leq y \leq b_2 \right\}$

I don't think you will find the algorithm you're looking for (this is my guess). This is because the geometry of cubes in $\mathbb{R}^n$ and the geometry of the $n+1$ simplex changes drastically with $n$.

You can always find such a simplex though, that's easy. Take any simplex and just scale it up until it covers your set.

This reminds me of an old problem by originally posed by Borsuk. If you start with a set in $\mathbb{R}^n$ of diameter $1$, can you find a partition of the set into $n+1$ pieces, each having diameter less than $1$? The answer is yes for balls, but false for general sets in high dimensions.

 

[haruspex]

I think your construction generalises easily enough.
Pick a dimension, 4 say, for the "tent pole".
To form the base, expand the 3D cube [a1,b1]×[a2,b2]×[a3,b3]×[a4] by uniform magnification, preserving the centre:
[a1-s(b1-a1),b1+s(b1-a1)]×[a2-s(b2-a2),b2+s(b2-a2)]×[a3-s(b3-a3),b3+s(b3-a3)]×[a4] for some s > 0.
Form a straight line through the vertex (a1-s(b1-a1), a2-s(b2-a2), a3-s(b3-a3), a4) of the new cube and the vertex (a1, a2, a3, b4) of the old hypercube. Similarly for the other 7 vertices of the new cube: (b1+s(b1-a1), a2-s(b2-a2), a3-s(b3-a3), a4) to (b1, a2, a3, b4) etc. (Each line relates to one of the 8 choices (x, y, z, t) where each of x, y, z can be a or b.)
By similarity, the eight lines must intersect in a single point. I think you can calculate the coordinates of this point using any two of the lines. (Works in 3D.)

 

[jacobrhcp]

I believe the OP means the rectangle {(x, y) | a₁ < x₁ < a₂, b₁ < x₂ < b₂}

I believe it means the 4D box whose description is similar to the rectangle I described above (but in R⁴).

Now that I reread, I am sorry for how poor this question was phrased. What I mean is indeed the four-dimensional box:

\{(x_1,x_2,x_3,x_4)\in ℝ^4|a_1\leq x_1 \leq b_1, a_2\leq x_2 \leq b_2, a_3\leq x_3 \leq b_3, a_4\leq x_4 \leq b_4\}

And what I meant is not the cross product of the points (a_i, b_i), but of the intervals [a_i, b_i], where a_i\leq b_i.

And I wonder if you can find a simple formula or algorithm for 5 points in ℝ4 that contain the box.

Haruspex, thank you for your answer! But if I understand it correctly, you give a method to find 8 points that together contain the box completely? I think I need to puzzle on this some more =)

EDIT: But, repeating, indeed your method reduced from 8+1 for the 'tent pole' to 4+1+1 to 2+1+1+1=5. I will work it out. Thank you haruspex.

 

[haruspex]

Haruspex, thank you for your answer! But if I understand it correctly, you give a method to find 8 points that together contain the box completely? I think I need to puzzle on this some more =)
EDIT: But, repeating, indeed your method reduced from 8+1 for the 'tent pole' to 4+1+1 to 2+1+1+1=5. I will work it out.

No, I constructed 8 points from one of the 3D faces of the hypercube. Then 8 lines, each containing one of these points and one point from the opposite 3D face. These 8 lines intersect in the 9th point.