2
$\begingroup$

I've seen minimum-bend TSP studied, has anyone looked at max-bend TSP?

As a special case, I'm interested in the maximum number of turns a hamiltonian path can take in an $n \times n$ square grid.

I think it should be $n^2 - n$ for even $n$ and $n^2 - n - 1$ for odd $n$, but does anyone know a proof?

$\endgroup$
3
  • $\begingroup$ Hi Michael, would you care spelling out the meaning of the acronym TSP? I don't know what it stands for. $\endgroup$ Aug 11, 2011 at 20:39
  • $\begingroup$ I suspect he is using Traveling Salesman Path for Hamiltonian path. In many contexts, bends don't make much sense, but on the grid it becomes an interesting problem. I suspect some region argument (divide the grid into somewhat similar regions) might demonstrate the poster's conjecture. Gerhard "Ask Me Aboit System Design" Paseman, 2011.08.11 $\endgroup$ Aug 11, 2011 at 21:12
  • 1
    $\begingroup$ It's a serious breach of etiquette to post this here just hours after posting it to math.stackexchange math.stackexchange.com/questions/56861/… especially without acknowledging that you are doing so. Voting to close. $\endgroup$ Aug 11, 2011 at 22:40

1 Answer 1

1
$\begingroup$

Let me write $f(n) = n^{2}-n$ for even $n$ and $f(n) = n^{2}-n-1$ for odd $n$.

It's certainly the case that you can do at least as well as $f(n)$. More precisely, there is a path with $f(n)$ turns that ends up at the top right corner of the grid, and which arrived there from the point below that.

It's easy to check this for $n=2$ or $n=3$, and we can handle the rest by induction (the inductive step being the reason it's important to generate examples that end up at the top right corner).

Suppose we have a path that works for an $(n-2) \times (n-2)$ grid; I'll call it the $(n-2)$-path. We proceed by extending this $(n-2)$-path to an $n$-path.

Place the $(n-2)$-path at the top left corner of the $n \times n$ grid, leaving two columns to the right and two rows below the path. Start from the end point at the top right corner of the $(n-2)$-path. Extend the path two grid points rightwards, to the edge of the grid.

Now we split into two cases. If $n$ is even, snake down the right side of the grid, then across the bottom of the grid, finishing, via a down-move, at the bottom left corner. This procedure adds $4n-6$ bends to the original path, and so has $(n-2)^2 - (n-2) + 4n-6 = n^{2}-n$ bends. Finally, rotate the resulting path to give you a path with $n^{2}-n$ bends that ends with an up-move at the top right corner.

If $n$ is odd, then snake down the right side of grid. There is one small modification due to the oddness: you have to stop snaking just before you hit the bottom right. (At this point I wish I knew how to draw a nice picture.) Then resume snaking along the bottom of the grid. As before, you finish at the bottom left corner, via a down-move. Again, this adds $4n-6$ bends to the original path, so has $(n-2)^{2}-(n-2)-1 + 4n-6 = n^{2}-n-1$ bends. Finally, rotate the path to give an $n$-path that ends up at the top right.

There must be some neat argument to show that you can't do better than $f(n)$, but I can't see it yet...

$\endgroup$
1
  • $\begingroup$ By looking at corners, you can get $n^2 - 4$ as an upper bound for large n. I suspect the conjectured bound is tight. It might be provable by dividing the grid into diagonal regions, but I have not thought it through. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 $\endgroup$ Aug 11, 2011 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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