sorting - Ordered lattice point enumeration -

setup: let ei orthogonal basis n-dimensional euclidean space, suppose ei has irrational (l1) norm. let l set of points obtained taking linear combinations of ei coefficients in natural numbers (including zero). order points in l first l1-norm , lexicographically.

question: there efficient algorithm producing points in l in increasing order pre-defined bound? note not want produce points , sort them, rather want walk lattice in order.

observation: easy if ei orthonormal basis. instance, problem solved here. in principle similar work here, determining radii iterate on hard solving enumeration problem, isn't useful.

how this:

let l₁ , l₂ lists of vectors, l₁ list of visited/processed lattice vectors , l₂ list of lists of vectors visited next.

1. set l₁={ } , l₂ = {[0]}, 0 zero-vector.
2. let v smallest vector of first list in l₂.
3. visit/process vector v.
4. add list l={v+e₁,...,v+e_n} l₂, such lists sorted smallest element. generate v+e_i long norm smaller predefined bound.
5. insert v @ end of l₁ , remove front of first list l₂.
6. if first list empty, remove l₂. if not, move correct place.
7. if l₂ not empty, goto 2.

this algorithm requires e_i sorted norm small big.

this algorithm adds @ n vectors l₂ per round. let b predefined upper bound, there @ n^k-1 vectors going visit, k = 1+b/||e₁||. first ca. n^k' rounds, list of size n, k' = b/||e_n||. in total have store less n = n^k' + (n^k-1)/(n^k'+1) lists. can generate new list in o(n) , add place in l₂ in o(log n) (binary search correct place , link insert there).

so overall complexity o(n⋅n⋅log n), notice n number of vectors looking for.

notice: there faster algorithm, can try.