I am looking for an algorithm to compute the $n$ shortest lattice vectors in $\mathcal{R}^2$. The problem statement is as follows:
Given a lattice $L: \{ m \vec{u}+n\vec{v} \} \in \mathcal{R}^2$, a norm $\left\lVert\cdot\right\rVert$, and an integer $N>0$, compute a set of $N$ shortest lattice vectors $S$ such that if $\vec{x}\in S$, then for all $\vec{y} \notin S$, $\left\lVert\vec{y}\right\rVert \ge \left\lVert\vec{x}\right\rVert$. One may assume that $\vec{u}$ and $\vec{v}$ are reduced basis vectors returned from Gauss' algorithm.
Ideally, the algorithm can take an existing $S$ and expand it by adding in the next "ring" of vectors with the next greatest norm. I have a rough idea of how to go about doing this for the Euclidean norm; you can move along the perimeter of the already-found vectors and add in new vectors of minimal norm, but I am wondering if it is possible to generalize this to any norm. Even generalizing to $L_1$ or $L_\infty$ norms would be good.
Edit: Description of my algorithm for the $L_2$ norm.
The algorithm seeks to find the next ring of points with the next largest norm (radius from the origin) given an existing ring. We accomplish this by scanning along the "perimeter" of the existing ring, in only one of the dimensions since the other length in the other dimension is roughly known based on the equation of a circle.
- Assume you are given the reduced lattice basis vectors $\vec{u}$ and $\vec{v}$, integer coefficients $(a,b)$ such that $a \vec{u} + b\vec{v}$ is one of the points on the existing ring of radius $r$.
- Determine the maximum extent we need to scan in the $\vec{u}$ direction: Compute $m>0$ such that $\left\lVert m\vec{u}+n\vec{v} \right\rVert = r$ has no solution for any $n$. This is a simple quadratic equation. Round $m$ away from zero by one to be safe. The amount of time it will take to complete the scan is proportional to $m$.
- Initialize $r_b = \infty$, the radius of the best next candidate ring. Initialize the set $S$ of next ring points to empty.
- For each $i$ in $-m \le i \le m$, determine $j$ so that $r_c = \left\lVert i\vec{u}+j\vec{v} \right\rVert > r$. If $r_c \lt r_b$, then we found an even smaller ring: set $r_b = r_c$ and set $S = \{i,j\}$. Otherwise if $r_c = r_b$ we found another point on the ring and add $\{i,j\}$ to $S$. Otherwise, if $r_c \gt r_b$, do nothing.
A little thought should convince you that this works. This only works for the $L_2$ norm since it explicitly makes use of the shape of the equi-norm contours. For a general norm, the shape is not known ahead of time.