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?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ You might try an upper bound based on inscribing a cube inside a unit simplex. $\endgroup$
    – The Masked Avenger
    Commented Apr 7, 2015 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
    Commented Apr 7, 2015 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
    Commented Apr 7, 2015 at 15:55
  • 1
    $\begingroup$ I asked the latter question here: mathoverflow.net/questions/139161/…. $\endgroup$
    – Jan Kyncl
    Commented Apr 9, 2015 at 2:36

5 Answers 5

Reset to default
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.

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.

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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Apr 24, 2015 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
    Commented Apr 25, 2015 at 5:41
  • $\begingroup$ Very clever to use the icosahedron in this fashion! $\endgroup$
    – Joseph O'Rourke
    Commented Apr 25, 2015 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
    Commented Apr 25, 2015 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
    Commented Apr 25, 2015 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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Apr 8, 2015 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
    Commented Apr 8, 2015 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
    Commented Apr 24, 2015 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.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .