Suppose I have a lattice grid of $m \times n$ points in the plane, with $m\leq n$. I want to traverse this grid in such a way as to minimize the total amount of turning that occurs. I am pretty sure that you can't improve on just traversing each row of $n$ points one at a time, turning 180 degrees to then go to the next row, which seems completely obvious, but I can't actually work out a formal proof of it. Does anyone have a reference or a solution strategy?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ The question mathoverflow.net/questions/261031/… listed under Related may have some useful information. $\endgroup$– Gerry MyersonCommented Jul 9 at 0:41
-
$\begingroup$ My proof won't immediately generalize to 3D, but the corresponding result may be true there as well: etsy.com/listing/1479087780/… $\endgroup$– Yaakov BaruchCommented Jul 14 at 5:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
(I assume that the OP wants to minimize is the number of turns rather than the total amount of absolute turning angles.)
If we restrict to moving only parallel to the axes, here is an elementary proof.
Assume there are $n$ rows and $m$ columns. Represent the traversing path by segments going from the center of one unit square to the center of the next and so on. There are then three (overlapping) types of unit squares with path-segments, according to the diagram pictured (notice that end-of-path squares are considered TURNs):
Trivial observation: any row of the rectangle containing an X-square must contain at least $2$ TURN-squares. Likewise any column containing a Y-square must contain at least $2$ TURN-squares.
Conclusion: if each row contains at least one X-square, then there are at least $2n$ TURN-squares. Otherwise there is one row consisting entirely of Y-squares, in which case each column contains at least one Y-square, and then there are at least $2m$ TURN-squares. Since $2$ of the $2n$ or $2m$ TURN-squares are end-of-path squares, there are at least $\min(2n,2m)-2$ true turns, as expected.
ADDENDUM 7/8/2024. (As per comments, if I understood correctly.)
If any piecewise linear path in the plane is allowed (self-crossing, not grid-aligned, not contained in the minimal rectangle around the lattice points), then the above result doesn't hold. The picture shows an example for $m=n=4$, with only $5$ turns:
answered Jul 13 at 22:44
-
$\begingroup$ Thank you for the reply! Do you see any way to generalize this where one doesn't have to take only right hand turns? $\endgroup$ Commented Jul 31 at 22:05
-
$\begingroup$ @TomSolberg : I don't understand this last question. Nowhere is there any mention of right or left hand turns... There are paths with the minimal number $n-2$ of turns containing only left turns, or only right turns, or anything in between. $\endgroup$ Commented Aug 2 at 15:20
-
$\begingroup$ Sorry, I was horribly unclear. I meant to say: as I understand it, your proof bounds the number of squares that have a turn in them, if we restrict ourselves only to movement in the north/south/east/west direction. It feels silly, but I'd like to bound the total turning if we assume any directions allowed, like there aren't any HORIZONTAL or VERTICAL squares because it's always moving at a 45-degree angle or something like that. Does that make sense? $\endgroup$ Commented Aug 2 at 20:55
-
$\begingroup$ Too tired to edit, but there is a simpler example where the $3\times 3$ lattice can be traversed by a path with only 3 turns. $\endgroup$ Commented Aug 7 at 1:27
-
$\begingroup$ Thanks for bearing with me -- I just saw your edits and in fact I am indeed interested in minimizing the total amount of absolute turning angles. I'm picturing a vehicle that can move rapidly in a straight line, but where turning takes a long time. $\endgroup$ Commented Aug 7 at 8:59