3
$\begingroup$

There is an algorithm that give us cuboids in $\mathbb{R}^3$, say $Q_1,Q_2,\ldots$, such that $\cup_{i=1}^{\infty} Q_i$ is the simplex with vertices $(0,0,0), (1,0,0) , (0,1,0), (0,0,1)$, and the $Q_i$'s are almost disjoint (i.e $\lambda(Q_i\cap Q_j)=0$ if $i\neq j$)?

In $\mathbb{R}^2$ there are many easy ways to fill a triangle with almost disjoint-rectangles but I had not find the way to generalize this to higher dimensions. Do you have any ideas?

This will be very helpful, for example, to approximate the cumulative distribution function of a sum of 3 or more random variables that are not necessarily independents.

Improve this question
$\endgroup$
1
  • $\begingroup$ Do you mean with "is the simplex.." really, covers the interior of the simplex. Any cube can only contain one point of the face opposing $(0,0,0)$, and hence the whole closed simplex cannot be covered by finitely many points. $\endgroup$
    – HenrikRüping
    Commented Feb 19, 2010 at 13:01

2 Answers 2

Reset to default
3
$\begingroup$

OK, since we finally have figured out what Andres is asking and since 600 characters is a bit too restrictive, I'll post this as an answer.

The following Asymptote code will draw the filling except I used the size 4 simplex instead of size 1 one here:

size(400);
import three;
import graph3;


pen[] q={red,green,magenta,blue,black};
q.cyclic(true);

int N=4;
triple O=(0,0,0),A=(4,0,0),B=(0,4,0),C=(0,0,4);
draw(O--A--B--C--A--C--O--B);
for(int n=0;N>n;++n)

{
real s=1/2^n;
for(real x=4-3*s;x>=0;x-=2s)
for(real y=4-x-3*s;y>=0;y-=2s)
{
draw(shift((x,y,4-x-y-3*s))*scale3(s)*unitcube,q[n]);
draw(shift((x-s,y,4-x-y-3*s))*scale3(s)*unitcube,q[n]);
draw(shift((x-s,y+s,4-x-y-3*s))*scale3(s)*unitcube,q[n]);
draw(shift((x-s,y,4-x-y-2*s))*scale3(s)*unitcube,q[n]);
}
}

The unitcube is just $[0,1]^3$, the rest should be self-explanatory.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you fedja, that's exactly what I was looking for. Now I will try to generalize this idea for greater dimensions. $\endgroup$
    – Andrés
    Commented Feb 22, 2010 at 10:05
1
$\begingroup$

Here's a (highly nonoriginal) method: overlay a finite hyperplane grid onto the region of interest. For R^2 this divides the plane into rectangles, for R^3 into cuboids (a.k.a rectangular parallelipipeds), and into higher dimensional intervals for the space of your choice. Now, mark all those bounded grid areas which lie fully inside your region; if you have some space left over not inside a marked area, add finitely many more hyperplanes to your grid, and repeat. Doing this countably many times will get you within epsilon in measure to your region. I leave the formalizing of the algorithm to you.

Oops, in using the word measure I gave it away. Cf. Lesbesgue or Riemann for technical details.

Gerhard "Ask Me About System Design" Paseman, 2010.02.17

Improve this answer
$\endgroup$
10
  • $\begingroup$ The interesting question is how well you can approximate the simplex with $n$ cuboids. All constructions that come to my mind leave the volume of order $n^{-1/2}$ uncovered. Does anybody see a simple reason why we cannot do better? $\endgroup$
    – fedja
    Commented Feb 18, 2010 at 3:34
  • $\begingroup$ Gerhard, actually I was thinking more in a "real world" programmable algorithm, but thank you anyway. And fedja, how did you arrive to this conclusion? What constructions do you have in mind? $\endgroup$
    – Andrés
    Commented Feb 18, 2010 at 12:39
  • $\begingroup$ The classical exhaustion that works for any domain is by maximal diadic cubes contained in the domain. It is a bit less pleasant to program than Gerhard's Riemann sum exhaustion (which, in your case, is just $[\frac{j-1}n,\frac jn]\times[\frac{k-1}n,\frac kn]\times[0,\frac{n-j-k}n]$, $j,k>0; j+k\le n$), but may be advantageous for some purposes. Both leave the uncovered area inversly proportional to the square root of the number of cuboids. $\endgroup$
    – fedja
    Commented Feb 18, 2010 at 14:39
  • $\begingroup$ Maybe I did not explain well the problem, I'm not looking for an algorithm like the one given by the Riemann sum because in that case when you have finish with the n^2 cuboids (following your program) and you want a better approximation then you have to start again (with a slightly different version of the algorithm) and construct for example (n+1)^2 new cuboids (which are obviously not disjoint of the ones constructed before). I'm looking more for a generalization of this construction in $\mathbb{R}^2$: To fill the triangle with vertices (0,0), (0,1) and (1,0) you can put: $\endgroup$
    – Andrés
    Commented Feb 18, 2010 at 16:45
  • $\begingroup$ $Q_1 = [0,\frac{1}{2}]\times[0,\frac{1}{2}], Q_2 = [\frac{1}{2},\frac{3}{4}]\times[0,\frac{1}{4}], Q_3=[0,\frac{1}{4}]\times[\frac{1}{2},\frac{3}{4}], Q_4=[\frac{3}{4},\frac{7}{8}]\times[0,\frac{1}{8}]...$ and so on. $\endgroup$
    – Andrés
    Commented Feb 18, 2010 at 16:48

You must log in to answer this question.

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