Consider the following problem: You're given set of lattice points $\{a_i\}_{i=1}^n=\{(x_i,y_i)\}_{i=1}^n$. You have to cover it with lattice square grid having minimum possible number of nodes.

That is, you have to find integer $m\in\mathbb Z_+$ and such point $a_0\in \mathbb Z^2$ and directions $r_1,r_2 \in \mathbb Z^2$ that $(r_1,r_2)=0,|r_1|=|r_2|$ and set of points $S=\{a_0+u\cdot r_1 + v \cdot r_2\}_{u,v=0}^{m-1}$ covers all $a_i$. Among all such you have to find one that minimizes number of points in the grid, i.e. $m\times m$.

This problem has simple and effective solution which is, in short:

(I encourage you to think of it before heading under the spoiler)

To consider $a_i$ to be the gaussian numbers, then use $r_1=\gcd(a_2-a_1,a_3-a_1,\dots,a_n-a_1)$ and $r_2=i\cdot r_1$.

After I met the problem, I thought about its generalization to the three-dimensional case, i.e. given $\{a_i\}_{i=1}^n = \{(x_i,y_i,z_i)\}_{i=1}^n$ to find such $m\in \mathbb Z_+, a_0,r_1,r_2,r_3 \in \mathbb Z^3$ that

$$\forall i \hookrightarrow a_i \in S=\{a_0+u\cdot r_1 + v\cdot r_2 + w\cdot r_3\}_{u,v,w=0}^{m-1},\\(r_1,r_2)=(r_1,r_3)=(r_2,r_3)=0,\\|r_1|=|r_2|=|r_3|$$ which minimize $m^3$. Same approach seems inappropriate, but is there a way to solve the problem?

UPD: There are specific restrictions for three lattice vectors to be orthogonal having same length. $[r_1,r_2]$ is also lattice vector which is collinear with $r_3$. Thus $[r_1,r_2]=\alpha r_3$ where $\alpha\in\mathbb Q$. But $\alpha^2=\dfrac{|[r_1,r_2]|^2}{|r_3|^2}=|r_3|^2 \in \mathbb Z\implies|r_3|=|\alpha|\in\mathbb Z$. So all three vectors must also have integer length and, according to Pythagorean quadruple article can be represented as columns in

$$k\begin{pmatrix}m^2+n^2-p^2-q^2 & 2np-2mq & 2mp+2nq\\ 2mq+2np & m^2-n^2+p^2-q^2 & 2pq-2mn\\ 2nq-2mp & 2mn+2pq & m^2-n^2-p^2+q^2\end{pmatrix}$$

For $k,m,n,p,q \in \mathbb N \cup \{0\}$.