Timeline for Snake algorithm that minimizes straight lines
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2020 at 22:47 | history | edited | RobPratt | CC BY-SA 4.0 |
deleted 8 characters in body
|
| Nov 24, 2020 at 21:42 | comment | added | RobPratt | I am using integer linear programming, which yields lower bounds via relaxation. | |
| Nov 24, 2020 at 20:39 | comment | added | Wolfgang | ... But it seems tricky to capture what happens at the boundaries between two "zigzag parts". E.g. it makes sense to consider the cross at the right in your $10\times10$ loop as the union of 3 such zigzag parts (kind of direction changes), yet the straight segments are not between them, though at least 2 of the 3 are obviously required. | |
| Nov 24, 2020 at 20:16 | comment | added | Wolfgang | Thank you for the $10\times14$ example, so for reasons of parity, $f(10,14)$ is $12$ or $14$. I had thought your program does some kind of exhaustive search. (BTW, how can you know it is bigger than $10$? - From the various examples, it is now obvious that a lower bound is given by the number of "zigzag parts" in the loop, as each "corner" between them needs at least one straight segment to link them without self-overlap). This argument shows that $f$ is not bounded, in fact it seems well possible that it yields $f(a,b)\ge\min(a,b)$. | |
| Nov 24, 2020 at 17:11 | history | edited | RobPratt | CC BY-SA 4.0 |
added 145 characters in body
|
| Nov 24, 2020 at 8:47 | comment | added | Wolfgang | Nice! Your $12\times12$ solution yields immediately $f(4a,2b)\le4a$ by cloning the 4 columns #3 to 6 (with then tweaking 3 segments to reproduce the inner $8\times4$ pattern to the left), which increases $f$ each time by $4$. $\quad$ What does your program yield for $10\times14$? | |
| Nov 23, 2020 at 22:40 | history | edited | RobPratt | CC BY-SA 4.0 |
added 139 characters in body
|
| Nov 20, 2020 at 1:57 | history | edited | RobPratt | CC BY-SA 4.0 |
edited body
|
| Nov 19, 2020 at 20:57 | history | answered | RobPratt | CC BY-SA 4.0 |