Summary: We study here algorithms that determine successive minima in integer lattices of lower dimensions (\(n=2\) or \(n=3\)). We adopt an affine point of view that leads us to a better understanding of the complexity of Gauss’ algorithm and we can exhibit its worst-case input configuration. We then propose for the three dimensional case a new algorithm that constitutes the natural generalisation of Gauss’ algorithm. We build in polynomial time a “minimal” basis of the lattice and we also get a new structural result - on hyperacute tetrahedra. Furthermore, our algorithm has a better computational complexity that of the LLL algorithm in the 3-dimensional case.
For the entire collection see [Zbl 1209.00079].