# What is the minimum number of line segments that need to be made to cross all points on a $n \times m$ grid?

Given a grid of $n \times m$ points, on a sheet of paper, what's the minimum amount of lines (which can extend infinitely) required to pass through each point, that you can draw without lifting a pencil?

Sample grid and answer: Connect the dots

Note: Lines are of less width then points are radius, all lines must be straight.

• Could we just say that the points are of zero radius and the lines are of zero width? Otherwise the answer is "technically" 1 because you can always have the dots large enough that they overlap and you can just put a line through their intersection. Also, must the lines be end to end as stated in the puzzle you linked? (if not it's trivial) Sep 23 '15 at 3:39
• @Ben See the note Sep 23 '15 at 9:32
• @warspyking Well, your note is (a) grammatically incorrect (b) difficult to understand. Could you please state the question in a more elaborate form, so we can atleast understand it (and the edit it for you)? Sep 23 '15 at 12:43
• Basically I give you a grid of dots, and without lifting your pencil you have to draw over every dot with nothing but straight line segments. (The grid is $n \times m$) Sep 24 '15 at 2:13
• I have voted to close this question as unclear. If you address @ghosts_in_the_code's questions and modify the question, I will retract it. Sep 29 '15 at 18:25

I hope the lines are not required to intersect.

We want maximum number of points on each line. We can have a maximum of $m$ points on it (for $m\geq n$). Hence we draw $n$ parallel lines, each with $m$ dots.

• Even if the lines are required to intersect, because the points are not restricted to zero radius, you can always tilt the lines such that the $n$ lines are in a zigzag formation. Sep 23 '15 at 7:17
• I think @warspyking meant that (a) the points are of zero-radius (b) the lines must form a continuous curve. We'll have to wait and see. Sep 23 '15 at 7:23
• See the Note ${}$ Sep 23 '15 at 9:32

This is my hypothesis, but I haven't figured out how to prove it yet:

For $m = n$, the answer is

$2(n-1)$. This employs the solution given in the linked question, of basically using the well-known four-line solution for a $3\times3$ grid, and then extending a square spiral outward to encompass the other dots:

Any other solution (e.g. using a triangle spiral instead of a square) doesn't seem to improve on this number.

For $m > n$, the solution is

$2n-1$. There doesn't appear to be any more efficient solution than just drawing a spiral or zigzagging across the rows:

or

• Extending the answer to another related question, I think the answer is $m+n-2$ for $m+n\geq 5$ (the answer is obviously 1 if either m or n equals 1, and 3 if m=n=2). Feb 25 at 7:20