18
$\begingroup$

The volume of an $n$-dimensional simplex of unit edge length is $$V(n) = \frac{\sqrt{n+1}}{n! 2^{n/2}} \;,$$ so at least $\lceil 1/V(n) \rceil$ such simplices are needed to cover the unit $n$-cube.

Q1. What is an upperbound on the number of unit simplices needed to cover a unit $n$-cube?

I suspect that the $1/V(n)$ lowerbound is weak; perhaps there is no $c>0$ such that $c/V(n)$ is an upperbound?

For $n{=}2$, $1/V(2)=4/\sqrt{3} \approx 2.3$, but $4$ equilateral triangles are needed. For $n{=}3$, $1/V(3)=6\sqrt{2} \approx 8.5$; I don't know how many tetrahedra are needed to cover the cube.

Q2. How many unit tetrahedra are needed to cover a unit cube?

$\endgroup$
  • 4
    $\begingroup$ You might try an upper bound based on inscribing a cube inside a unit simplex. $\endgroup$ – The Masked Avenger Apr 7 '15 at 14:25
  • $\begingroup$ @TheMaskedAvenger: Nice idea! It doesn't seem to be known what is the largest cube inscribed in a regular simplex. Another nice question. $\endgroup$ – Joseph O'Rourke Apr 7 '15 at 15:13
  • $\begingroup$ True, but the latter question has a nice candidate based on the height h of the n+1 simplex. If c_n is the side length for a cube in scribed in an n simplex, a lower bound for c_n+1 (=c) comes from the relations c +rh=h and c= rc_n. $\endgroup$ – The Masked Avenger Apr 7 '15 at 15:55
  • 1
    $\begingroup$ I asked the latter question here: mathoverflow.net/questions/139161/…. $\endgroup$ – Jan Kyncl Apr 9 '15 at 2:36
4
$\begingroup$

A cube of side $1/\sqrt{2}$ can be covered by $5$ unit tetrahedra (one using four of the cube's vertices, and the reflections of that one across each of its faces). $8$ of those cubes can cover the unit cube, so we need at most $40$ tetrahedra that way.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

I'm now thinking the answer is 22, or very close to it. Put tetrahedral caps on each corner of the unit cube, and reflect about the base to place a corresponding interior tetrahedron, accounting for 16. After observing how an interior tetrahedron maximally intersects a corner cube of length 1/2, we see remaining 6 square pyramids (one on each face of the unit cube) of height less than 1/2 and length of base sqrt(2) - 1. I'm thinking each will fit inside a unit tetrahedron. Even if I am wrong, such a pyramid should fit into a union of two tetrahedra, giving an upper bound of 28.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

If I place a unit-edge tetrahedron at each face of a unit-edge icosahedron, so that they share a face and the tetrahedron is pointed into the icosahedron, I get 20 tetrahdera that together cover the icosahedron. I can now place a unit cube in such a way that nearly all of it is covered by the icosahedron. Only two corners will stick out, and we can easily cover them by adding two more tetrahedra. Therefore, a unit cube can be covered by 22 tetrahedra.

Coordinates for the cube:

{{-0.250201, -0.657675, -0.504839}, {-0.507631, -0.535251, 0.453671}, {-0.439869, 0.308569, -0.679191}, {-0.697299, 0.430994, 0.279319}, {0.697299, -0.430994, -0.279319}, {0.439869, -0.308569, 0.679191}, {0.507631, 0.535251, -0.453671}, {0.250201, 0.657675, 0.504839}}

Coordinates for the icosahedron:

{{0., 0., -0.951057}, {0., 0., 0.951057}, {-0.850651, 0., -0.425325}, {0.850651, 0., 0.425325}, {0.688191, -0.5, -0.425325}, {0.688191, 0.5, -0.425325}, {-0.688191, -0.5, 0.425325}, {-0.688191, 0.5, 0.425325}, {-0.262866, -0.809017, -0.425325}, {-0.262866, 0.809017, -0.425325}, {0.262866, -0.809017, 0.425325}, {0.262866, 0.809017, 0.425325}}

cube in an icosahedron

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you push the cube to one side and get 21? You can cover a large bit of the corner with one tetrahedron. $\endgroup$ – The Masked Avenger Apr 24 '15 at 23:19
  • $\begingroup$ Even cooler (to the point of freaky) would be to push 18 of the tetrahedra in and pull the other two out just enough to cover. Probably not enough room though. $\endgroup$ – The Masked Avenger Apr 25 '15 at 5:41
  • $\begingroup$ Very clever to use the icosahedron in this fashion! $\endgroup$ – Joseph O'Rourke Apr 25 '15 at 11:58
  • 1
    $\begingroup$ @TheMaskedAvenger It's possible that you can push one of the corners in without pushing any of the other corners out, but I haven't been able to. Pulling the tetrahedra that the corners sticks out of out does sound promising. $\endgroup$ – Yoav Kallus Apr 25 '15 at 15:13
  • $\begingroup$ These don't seem to be regular tetrahedra; the edges that include the center have length shorter than 1. Edit: Oops, nevermind, that means regular ones are even larger and thus cover. Ignore this. $\endgroup$ – Harry Altman Apr 25 '15 at 15:16
2
$\begingroup$

Following the suggestion of TMA just for Q2, I found a calculation and beautiful graphics by Anders Kaseorg at this website


     
showing that a cube of sidelength $x \approx 0.2959$ fits inside a unit tetrahedron in $\mathbb{R}^3$. Because $1/x \approx 3.4$, a $4 \times 4 \times 4 = 64$ arrangement of cubes cover a unit cube (with much to spare). So a unit cube can be covered by $64$ unit tetrahedra. Although there is considerable over-coverage (see below), a straightforward $3 \times 3 \times 3$ stacking does not suffice.
      CubeCoveredTetra
$64$ is surely much larger than the optimal.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If you take two tetrahedra, put them base to base, twist one 60 degrees, then smash them together, you might get something that covers a cube of side length close to 1/2. In any case, I'm guessing the required number of tetrahedra is close to 20. $\endgroup$ – The Masked Avenger Apr 8 '15 at 4:43
  • 1
    $\begingroup$ hmm. Two unit tetrahedra seem to cover a cube of side length root(2)/3. Add one for each face and edge of the unit cube, and I get 34 total. $\endgroup$ – The Masked Avenger Apr 8 '15 at 8:03
  • $\begingroup$ 20 unit-edge tetrahedra cover a unit-edge icosahedron, which nearly covers a unit-edge cube. Seems like you should be able to perturb that a bit and add a few tetrahedra to cover the cube completely. $\endgroup$ – Yoav Kallus Apr 24 '15 at 17:47
2
$\begingroup$

From the upper bound $\sqrt{2}n$ on the edge length of the smallest regular simplex containing the unit cube in $\mathbb{R}^n$, shortly outlined in the question Smallest regular simplex containing the unit cube in $R^n$, it follows that roughly $n^n2^{n/2}$ unit simplices are sufficient to cover the unit cube by translation.

This might be far from optimal, since the translation covering density of any convex body in $\mathbb{R}^n$ is only $n\ln{n} + n\ln\ln{n} + 5n$, due to Rogers. Moreover, it is known that the most economical covering cannot be lattice like. (For the details and references, please let me refer to Section 1.3 in P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, 2005.)

| cite | improve this answer | |
$\endgroup$

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.