Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  HenrikRüping Feb 19 '10 at 13:01
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you fedja, that's exactly what I was looking for. Now I will try to generalize this idea for greater dimensions. –  Andrés Feb 22 '10 at 10:05
add comment

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

share|improve this answer
    
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? –  fedja Feb 18 '10 at 3:34
    
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? –  Andrés Feb 18 '10 at 12:39
    
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. –  fedja Feb 18 '10 at 14:39
    
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: –  Andrés Feb 18 '10 at 16:45
    
$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. –  Andrés Feb 18 '10 at 16:48
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.