Timeline for 1 rectangle <= 4 squares
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2010 at 19:01 | history | edited | Mariano Suárez-Álvarez | CC BY-SA 2.5 |
Fix the code so that Markdown sees it as one block
|
| Mar 1, 2010 at 22:07 | comment | added | Yaakov Baruch | I just realized (fun exercise) that the set of inequalities derived from decomposing rectangles into 2 in all ways (cutting vertically or horizontally) imply the set of inequalities derived from splitting rectangles into 4. Since the first approach involves 5 nested loops instead of 6, it is MUCH faster for large grids. For a medium grid I timed a speed improvement 6x. | |
| Feb 27, 2010 at 21:01 | comment | added | TonyK | Not so in this case. I tried L = 2 in one direction and L = 4 in the other, for a 30 x 90 grid, and it still got stuck at 3.80. | |
| Feb 27, 2010 at 19:51 | comment | added | Yaakov Baruch | I suspect that |m|+|n|<L may produce better grids... but this is just a hunch. Similarly I suspect that lopsided grids (more points for, say, y than x) may be more effective than symmetric ones. | |
| Feb 27, 2010 at 19:22 | comment | added | TonyK | Now, here's a surprise: with L = 3, and a 56 x 56 grid, there is no improvement: it's still 3.8! And L = 4 is beyond my reach. | |
| Feb 27, 2010 at 18:18 | comment | added | Yaakov Baruch | 3.8 is stunning! One can also use this tool will small B's (instead of 1000), to find upper limits for 1x5, 1x6, 2x7 etc. (like the 3.5 we have for 1x4), and then based on that one can better focus a search for a higher low bound... With these low B's one of course has to make sure that the x and y array are sorted by value (or else create special cases in the code for when (x[m],y[n]) lies outside the rectangle defined by (x[i],y[k]) and (x[j],y[l]). | |
| Feb 27, 2010 at 17:07 | comment | added | TonyK | Now I am using generated grids: the x-grid is {mA + nB} + {0,A}, and the y-grid is {mA + nB} + {0, B}, for all m,n with |m| <= L and |n| <= L, for some parameter L. With L = 2, we get a 30x30 grid, and the iteration process results in a bound of 19/5 = 3.8 (!). I am going to try L=3, but it will be slow... | |
| Feb 27, 2010 at 9:50 | comment | added | TonyK | Using your enlarged x and y grids (18 x 32), and iterating as above, I can get down to 47/12 = 3.916666... By the way, if you are using the larger x grid in your above comment, then lo[5,6,12,19] should be lo[8,9,12,19]. | |
| Feb 26, 2010 at 12:42 | comment | added | Yaakov Baruch | I'll be off internet for next 28 hour. | |
| Feb 26, 2010 at 12:41 | comment | added | Yaakov Baruch | This is where I'm at now: KNOWN_BOUND=3.94445; TEST_BOUND=3.94; x grid as before y[0]=-3*B; y[1]=-2*B-A; y[2]=-2*B; y[3]=-2*B+A; y[4]=-B-2*A; y[5]=-B-A; y[6]=-B; y[7]=-B+A; y[8]=-B+2*A; y[9]=-3*A; y[10]=-2*A; y[11]=-A; y[12]=0; y[13]=A; y[14]=2*A; y[15]=3*A; y[16]=B-3*A; y[17]=B-2*A; y[18]=B-A; y[19]=B; y[20]=B+A; y[21]=B+2*A; y[22]=B+3*A; y[23]=2*B-2*A; y[24]=2*B-A; y[25]=2*B; y[26]=2*B+A; y[27]=2*B+2*A; y[28]=3*B-A; y[29]=3*B; y[30]=3*B+A; y[31]=4*B; N=31; ... lo[5,6,12,19]=TEST_BOUND; (and it succeeded - 3.94 is a new limit. But awk is killing me.) | |
| Feb 26, 2010 at 12:25 | comment | added | TonyK | What happens if you use 71/18 instead of 4 in your larger grid, Yaakov? | |
| Feb 26, 2010 at 12:23 | comment | added | TonyK | I have been trying this idea in parallel with you. If we replace 4 with 154/39 as the maximum value for all rectangles, then we get a new, smaller limit, r say. And now we can replace 154/39 with r, and so on. I have iterated this process by hand, and it reaches a limit of 3.944444... = 71/18. The question is whether this iteration is a substitute for using a larger grid, or whether a larger grid is really needed to get better limits. | |
| Feb 26, 2010 at 11:56 | comment | added | Yaakov Baruch | Another update: assuming the already proven limits of -3.95 and +3.95 for all rectangles, then 3.945 is a limit! (This works even with the original 12x18 grid.) | |
| Feb 26, 2010 at 11:42 | comment | added | TonyK | I converted it to C++ before I ran it. It didn't take long. I will play around with the grid sizes when I have some time. | |
| Feb 26, 2010 at 11:31 | comment | added | Yaakov Baruch | Tony, thank you. I tried enlarging the x grid to {-2B,-B-A,-B,-B+A,-2A,-A,0,A,2A,B-A,B,B+A,2B}+{0,A} but 3.945 is still out of reach. By the way, I find mawk to be a little faster than either awk or gawk (of course perl would be even better, or C if one had the patience). | |
| Feb 26, 2010 at 10:34 | comment | added | TonyK | I have used your program to do a binary search for the limiting value. For the grid that you use, it turns out to be exactly 154/39 = 3.9487... | |
| Feb 26, 2010 at 9:03 | comment | added | Yaakov Baruch | This a preemptive comment: one could argue that I'm proving the result only for thin enough rectangles (as hinted by my pick of a huge B=1000). However this is not essential. If one thinks in term of "negative rectangles" it is easy to see that set of constraints imposed by the key decomposition of one rectangle in 4 sub-rectangles, remains the same. | |
| Feb 26, 2010 at 8:39 | history | edited | Yaakov Baruch | CC BY-SA 2.5 |
added 163 characters in body; deleted 4 characters in body
|
| Feb 26, 2010 at 3:03 | history | edited | Yaakov Baruch | CC BY-SA 2.5 |
edited body
|
| Feb 26, 2010 at 2:36 | history | answered | Yaakov Baruch | CC BY-SA 2.5 |