Compute lattice points in rectangular region

Question

Let $M \subset \mathbb R^2$ be a lattice of rank $2$ given by a basis $b_1,b_2\in \mathbb R^2$. So $M = \mathbb Z b_1 +\mathbb Z b_2$. I'm looking for an algorithm which computes every lattice point in a rectangular region $[a,b] \times [c,d]$. So we are interested in the finite set $M \cap ([a,b] \times [c,d])$.

In case $b_1 = (r_1,0)$ and $b_2 = (0,r_2)$ for $r_1,r_2 \in \mathbb R$ that would be quite simple. But my basis is of course not in that form (in fact for my lattices there is no basis of that form since $(0,0) \in M$ is the only lattice point with a zero in a coordinate).

Do you have ideas how to proceed? I guess I should transform my basis somehow into a basis which is more suitable. But what does more suitable mean in this situation and how can I do that?

Answer 1

Let $m=(m_1,m_2)\in M$. You can represent $m=(m_1b_{11}+m_2b_{21}, m_2b_{12}+m_2b_{22})\in\mathbb R^2$. Now proceed to find all pairs $(m_1,m_2)\in\mathbb Z^2$.

Answer 2

We have a rank-$2$ lattice in $\mathbb R^2$

$$\mathcal L := \left\{ z_1 \begin{bmatrix} |\\ \mathrm b_1\\ |\end{bmatrix} + z_2 \begin{bmatrix} |\\ \mathrm b_2\\ |\end{bmatrix} : z_1, z_2 \in \mathbb Z \right\} = \{ \mathrm B \mathrm z : \mathrm z \in \mathbb Z^2 \} = \mathrm B \mathbb Z^2$$

where $2 \times 2$ matrix $\mathrm B = \begin{bmatrix} | & |\\ \mathrm b_1 & \mathrm b_2\\ | & |\end{bmatrix}$ has full column rank and, thus, is invertible, and a rectangle

$$\mathcal R := [c_1, d_1] \times [c_2, d_2]$$

We would like to determine the cardinality of the finite set $\mathcal L \cap \mathcal R$, which we denote by $| \mathcal L \cap \mathcal R |$.

There is a quadrilateral $\mathcal Q \subset \mathbb R^2$ such that $\mathcal R = \mathrm B \mathcal Q$. Hence,

$$| \mathcal L \cap \mathcal R | = | \mathrm B \mathbb Z^2 \cap \mathrm B \mathcal Q| = | \mathbb Z^2 \cap \mathcal Q|$$

Since the vertices of $\mathcal R$ are

$$\left\{ \begin{bmatrix} c_1\\ c_2\end{bmatrix}, \begin{bmatrix} d_1\\ c_2\end{bmatrix}, \begin{bmatrix} c_1\\ d_2\end{bmatrix}, \begin{bmatrix} d_1\\ d_2\end{bmatrix} \right\}$$

the vertices of $\mathcal Q$ are

$$\left\{ \mathrm B^{-1} \begin{bmatrix} c_1\\ c_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} d_1\\ c_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} c_1\\ d_2\end{bmatrix}, \mathrm B^{-1} \begin{bmatrix} d_1\\ d_2\end{bmatrix} \right\}$$

Taking the minimum and the maximum along each axis, we obtain a minimal bounding box $\mathcal B$ that contains $\mathcal Q$. Hence, $| \mathbb Z^2 \cap \mathcal B|$ gives us an upper bound on the cardinality $| \mathbb Z^2 \cap \mathcal Q |$. Using $2$ for loops, we can count the number of integer points inside $\mathcal Q$ and, thus, obtain $| \mathbb Z^2 \cap \mathcal Q | = | \mathcal L \cap \mathcal R |$.

Answer 3

There are two relevant metrics in the problem, one is in ${\Bbb R}^2$ coming from the rectangle, the second in ${\Bbb Z}^2$ induced by your lattice basis.

In order to avoid carrying around on annoying constants (from the rectangle), the first reduction is to multiply $x,y$ coordinates by $1/(b-a)$ and $1/(d-c)$, respectively. Your rectangle then becomes a unit square centered at $C=\left( \frac{a+b}{2(b-a)}, \frac{c+d}{2(d-c)}\right)$. For the lattice basis in these new coordinates we write: $$ (b_1\;\; b_2) = (e_1\;\; e_2) \left( \begin{matrix} u_1 & v_{1} \\ u_2 & v_2 \end{matrix} \right)$$ with $e_1,e_2$ being the canonical basis in ${\Bbb R}^2$. The idea is now to perform change of lattice basis in order to make $b_1,b_2$ as 'orthogonal' as possible (with respect to the Euclidean metric, since we have rescaled the rectangle to a square). Thus we multiply on the right with integer matrices of determinant $\pm 1$ (to preserve the basis property) in order to reduce the angle between $b_1$ and $b_2$. A bit like Gram-Schmidt orthogonalization except that we have to stick to integer matrices.

A kind of Euclidean algorithm:

Order first $b_1$ and $b_2$ so that $|b_1| \geq |b_2|$. Now, determine the integer $n$ that minimizes the length of $$ b'_1 = b_1 - n b_2$$ Also set $b'_2=b_2$ and reverse the roles of $b_1$ and $b_2$, repeating the algorithm until $|b_1| |b_2|$ becomes smaller than or equal to $2|\det (b_1 \;\; b_2)|$. Note that the determinant is preserved under the algorithm and that the algorithm terminates. When terminated the angles between the resulting vectors $(b_1,b_2)$ is at least $60$ degrees.

It follows that (if I didn't make a mistake in the calculations): $$ \frac{1}{4} \left( n_1^2 |b_1|^2 + n_2^2 |b_2|^2\right) \leq \left|n_1 b_1 + n_2 b_2\right|^2 \leq \frac{7}{4} \left( n_1^2 |b_1|^2 + n_2^2 |b_2|^2\right)$$ If centered at the origin the left hand inequality shows that is suffices to look at points with coordinates $|n_1|\leq 2/|b_1|$ and $|n_2|\leq 2/|b_2|$. I leave it to you the case when centered at a different point. Asymptotically, when both $|b_1|$ and $|b_2|$ are much smaller than one, the right hand inequality shows that our method checks at most a factor of $\sqrt{7}$ too many points. The constant is probably not optimal, though.