Timeline for Reduce the total internal border of a set of touching rectangles (using graphs)
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2018 at 7:25 | comment | added | jozamm | I will code a solution these days and give an update | |
| Dec 16, 2018 at 19:38 | comment | added | John | Indexing from 0, make a 2x2 box with lower left hand corner in column index 1 and row index 10, and a 2x2 box with lower left hand corner in column index 3 and row index 11. This removes 5 internal boundaries and replaces them with 4. So you can improve on the result, but not by a local greedy improvement since either one of those is temporarily worse. I don't know the optimal, I just know that my solution ain't it :). | |
| Dec 15, 2018 at 19:33 | comment | added | jozamm | What is not optimal? | |
| Dec 15, 2018 at 19:05 | comment | added | John | By the way, this is definitely not optimal. | |
| Dec 14, 2018 at 16:41 | comment | added | John | I now have a counter example to the largest area triangle being the best first choice, by the way: make a column 1 cell wide and 100 units high. Then, to the bottom two cells of the column add a 1 x 2 column off the side (making a sort of L shape) so that the bottom has a 2x2 square. The optimal is to cut that 2x2 square off as one rectangle and the remaining 1x98 column as a second rectangle leading to a score of 1. However, initially, the largest area rectangle I can make is the 1x100 initial column, but cutting this way gives me a sub-optimal score of 2. | |
| Dec 14, 2018 at 16:19 | history | edited | John | CC BY-SA 4.0 |
Added image of the final output.
|
| Dec 14, 2018 at 16:03 | history | edited | John | CC BY-SA 4.0 |
added code for the "real world" example
|
| Dec 14, 2018 at 15:50 | history | edited | John | CC BY-SA 4.0 |
added code sample
|
| Dec 14, 2018 at 14:03 | comment | added | John | My analysis is pretty coarse-grained. Intsead of naively generating all n^4 rectangles, you could imagine growing rectangles from a lower left-hand corner and generating all valid rectangles without generating any invalid ones. Then if $w$ and $h$ are the maximum width and height of any given rectangle and $m$ is the number cells in your polyomino, your only looking at $O(mwh)$ iterations, which sounds a lot better. And there's almost certainly some more clever algorithm you could use to find the largest rectangle that can be grown from each square. | |
| Dec 14, 2018 at 13:58 | comment | added | John | I think you almost certainly need to check all possible rectangles, not just the largest (in fact, what does "largest" mean here? By area? By Dimensions? I'm not sure either are completely relevant since what we care about is how many border edges are internal to the polyomino, not the size). For example, in my figure above, you'd also need to check the rectangle that has the same lower left-hand corner but is only two cells wide and 5 cells high. | |
| Dec 14, 2018 at 5:57 | comment | added | jozamm | From where do the n^4 comes, Basically I need to start from each rectangle and see the largest valid rectangle that can be created? | |
| Dec 13, 2018 at 21:56 | history | answered | John | CC BY-SA 4.0 |