How to cover integer pairs with lines efficiently?

Question

Your goal is to to "tag" all points in $\mathbb{Z}^2$.

At each step $i$ you can choose $(a_i,b_i)\in\mathbb{Z}^2$ and "tag" all points $S_{a, b, i} =\{(a - ik, b - k)|k\in\mathbb{Z}\}$

The objective is for each $i \in \mathbb{N}$ to choose $(a_i,b_i)$ such that:

1. you are sure that all points in $\mathbb{Z}^2$ will be tagged and
2. you do it in the most efficient way possible. Where efficiency means that at each step you retag the minimum number of points.

Can you find such a way?

I can think of a way to guarantee 2. but not 1. (Choose $(a_i,b_i) = (0, 1)$, in this case at each step you only retag one point [the $(0, 1)$] [note you will always retag at least one point], but the point $(1,1)$ will never be tagged)

and another that guarantees 1. but I am almost sure it is not efficient. e.g. you choose $(a_i,b_i)$ to take the famous spiral starting at $(0,0)$ that covers $\mathbb{Z}^2$.

Can you find a better way?

Answer 1

If I understand correctly, you want to create a spiral that touches all the integer points on the plane. This can accomplished readily in the complex plane where such points are called the Gaussian integers. The figure below shows the first 48 such points.

We can build up the spiral by the method of linkages, so-called because of its similarity to the old-fashioned surveyor chain, made up of articulated segments of unit length. For example, we repetitively go through a sequence of angles 0, 90, 180, and 270$^\circ$

On the first circuit the angles are 0,90,180,180,270,270.

On the second circuit this becomes 0,0,0,90,90,90,180,180,180,180,270,270,270,270,270.

On each subsequent circuit we add two more of each angle.

Now, the chain linkage works as follows

$$ \begin{align} & z_0=0\\ & z_1=1\\ & z_2=1+e^{i\pi/2}\\ & z_3=1+e^{i\pi/2}+e^{i\pi}\\ & z_4=1+e^{i\pi/2}+e^{i\pi}+e^{i\pi}\\ & z_5=1+e^{i\pi/2}+e^{i\pi}+e^{i\pi}+e^{i3\pi/2}\\ & \text{and so on} \end{align} $$

The algorithm is straightforward to develop and can probably be readily adapted to Cartesian coordinates. Obviously, the key is to know how many times to repeat each angle on each circuit, which we have worked out already.