Timeline for How to fill a simplex with almost disjoint cuboids?
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 19, 2010 at 20:19 | comment | added | Kevin P. Costello | My apologies, I was mistaken with my previous comment. | |
| Feb 19, 2010 at 19:40 | comment | added | Gerhard Paseman | I see a different picture. After I place the first cube (of edge length 1/3, else it does not fit inside) I get three simplices which have edge length 2/3, which are NOT disjoint. I can decompose this to 6 disjoint simplices, plus some truncated objects. If there is a nice recursion to handle the truncated objects, this would give a nice recursion to solve the posted problem. If you really see disjoint simplices, please post a picture or at least a list of vertex coordinates for all the parts making up the simplex. | |
| Feb 19, 2010 at 18:35 | comment | added | Kevin P. Costello | Why do you say the cubes will intersect nontrivially? It seems to me that at each step the greedy algorithm places 3^i cubes of side length (1/3)(2/3)^i, leaving 3^{i+1} disjoint simplices (each similar to the original) to place the next level of cubes in. The desired cubes don't intersect at a given level because they're being placed in different subsimplices. The disadvantage is that this method doesn't tile the whole interior of the simplex -- there's a Sierpinski like set of measure 0 that's never covered. | |
| Feb 18, 2010 at 19:02 | comment | added | Gerhard Paseman | Using just cubes of various sizes, I echo fedja's remark that starting with the largest cube and trying a greedy approach, (e.g starting with cube edge 1/3, then 3 of edge 2/9, etc.) it starts getting complicated because the desired cubes will start intersecting nontrivially. However, they are all cubes of rational lengths at rational coordinates, so you can choose one of the cubes that you are trying to place and subdivide it so as to place only that portion that avoids an already placed cube. Not pretty, but easily programmed. A tiling of the truncated simplex gives a handy recursion. | |
| Feb 18, 2010 at 18:53 | comment | added | Gerhard Paseman | It was not clear to me when I answered the question that 1) you were looking to tile the unit 3-simplex, 2) that you wanted cubes only and not prisms, and 3) that you wanted some optimal arrangement of cubes. Perhaps I have 1) 2) and 3) wrong, but fedja's remarks suggest 1) 2) and 3) to me. Regarding using a Riemann approach, and assuming prisms will work, you can iterate by partitioning the remainder after completing an iteration, not just starting all over from scratch with a finer partition. I also think that the error can be easily calculated if the prisms are parallel to the axes. | |
| Feb 18, 2010 at 16:48 | comment | added | Andrés | $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. | |
| Feb 18, 2010 at 16:45 | comment | added | Andrés | 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: | |
| Feb 18, 2010 at 14:39 | comment | added | fedja |
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.
|
|
| Feb 18, 2010 at 12:39 | comment | added | Andrés | 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? | |
| Feb 18, 2010 at 3:34 | comment | added | fedja | 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? | |
| Feb 17, 2010 at 18:41 | history | answered | Gerhard Paseman | CC BY-SA 2.5 |