Ordered lattice point enumeration

Question

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.

Setup: Let $e_{i}$ be an orthogonal (but not orthonormal) basis for $\mathbb{R}^{N}$. Define $\Lambda=\big\{\sum_{j=1}^{N}x_{j}e_{j}\mid x_{j}\in\mathbb{N}\big\}$ (where here I assume $0\in\mathbb{N}$). Now order the points in $\Lambda$ first by their $L^{1}$-norm, breaking ties lexicographically.

Question: Is there an efficient algorithm for producing the points in $\Lambda$ in order (up to some pre-defined bound)? Note that I want to walk this set in order, not produce it and then sort it.

Observations: This is easy to do if the $e_{i}$ are orthonormal. For instance, the problem is solved here. To make something like this work here, one would need to be able to efficiently answer the following. given positive real numbers $x_{1},x_{2},\ldots, x_{N}$, is there an efficient way to the numbers $\sum_{j=1}^{N}n_{j}x_{j}$ in increasing order, where $n_{j}\in\mathbb{N}$.

Answer 1

I am going to try to answer the version of the Observation which seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.

Answer 2

This question seems related to the case $N=2.$ I gave an answer suggesting that the continued fraction expansion of ${|e_2|}/{|e_1|}$ was the key. I haven't rechecked it. I'd venture that already the case $N=3$ would be much more difficult.