1
$\begingroup$

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\}$.

$\endgroup$
2
  • $\begingroup$ maybe you can do the same but with quaternions instead of conplex numbers. $\endgroup$
    – user35593
    Nov 6, 2017 at 16:13
  • $\begingroup$ I doubt that. Quaternions are not commutative and even though there is analogue of greatest common divisor in Hurwitz quaternions, it's not true for Lipschitz quaternions. Also in 3D space choosing some $r_1$ is not enough to fix $r_2$ and $r_3$. $\endgroup$ Nov 6, 2017 at 16:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.