Find $\{a, b, c\} \in \Bbb{Z}$ that minimise $\left\|v_0 + a\cdot v_1 + b\cdot v_2 + c\cdot v_3 \right\|$ where $\{v_0, v_1, v_2, v_3\} \in \Bbb{R}^3$

Question

I need find all pairwise shortest distance between any two atoms 3d tiled parallelepiped. I can calculated the exact solution for where $\{a, b, c\} \in \Bbb{R}$ and considering all 8 rounding directions but I'm not sure that would be correct.

Answer 1

A partial answer.

Let us work in a 2D framework where the ideas can be more easily expressed.

Let us consider the exact decomposition of $-v_0$ (the sign is important) with coefficients $A,B \in \mathbb{R}$:

$$-v_0=Av_1+Bv_2$$

(we assume $\{v_1,v_2 \}$ independent).

Now consider the lattice generated by all the $av_1+bv_2$ ($a,b \in \mathbb Z$), i.e., the set of parallelograms:

$$P_{pq}=\{av_1+bv_2 | p \le a \le p+1, q \le b \le q+1\}\tag{1}$$

At least one of them contains $-v_0$.

The first idea is to consider points

$$pv_1+qv_2, \ \ pv_1+(q+1)v_2, \ \ (p+1)v_1+qv_2, \ \ (p+1)v_1+(q+1)v_2, \tag{2}$$

But the prospection cannot be reduced to these 4 vertices as shown on the following counterexample :

Fig. : $F$ is the closest lattice point to $G$ though it is not one of the 4 vertices of the parallelogram countaining $G$!

A first answer is to propect for closest points along the strips containing this parallelogram (for example the gridpoints situated on the border of the strip between lines $FC$ and $EB$ and/or on the border of the strip between $EF$ and $BC$).

(Of course, for you it will be slabs in 3D).

A better idea, so I think, is not to abandon what has been said for (2) but after a [change of basis] (https://en.wikipedia.org/wiki/Lattice_reduction) for the lattice. Indeed, the problem in the counterexample I just gave is that the parallelograms are very elongated/slanted. Had we taken another equivalent basis (for example $v'_1=v_1;v'_2=v_1-v_2$ with determinant $\pm 1$, important), less "slanted" we would hopefully make rarer or impossible such counterexamples.