Suppose one has $N$ points belonging to an $n$-dimensional lattice $\mathcal{L}$, with $N > n$, and suppose one is sure that a basis for $\mathcal{L}$ is contained within those $N$ points. What's a (efficient) way to find a basis for $\mathcal{L}$?

For example, does the following naive algorithm work?: pick first the shortest vector among the $N$ (defining an origin somewhere). Then search for the shortest vector that is linearly independent from that one. Then find the shortest vector linearly independent from the first two, etc. Is that a basis?



You must log in to answer this question.

Browse other questions tagged .