Lattice Demonstration

This is an example of a 2D lattice. Drag the basis vectors v1 and v2 to see the effects. I have also implemented the Babai's (naive) algorithm for solving the closest vector problem. Tinker around to see if you can make it fail to produce the correct result.

Orthogonality Defect:

Angle between the basis:

Number of lattice points rendered per direction:

Show Fundamental Domain

Babai's Algorithm Demo

The algorithm used for the lattice basis reduction is the Gaussian (actually Lagrange's) basis reduction. This algorithm solves SVP completely for 2-dimensional lattices in quadratic time.

We also note that the algorithm can produce a basis with angle between the vectors be between 60 and 120 degrees, this means that the new basis is quite orthogonal.

The Babai's Algorithm tries to solve CVP by first writing the non-lattice point as a linear combination of the basis, then just round the coefficients to the nearest vector. In that way the algorithm will only output the lattice points "near" the non-lattice points.

function babai(){
    // Write the point as linear combination of basis vector

    const inv = inverse(v1.relX, v2.relX, v1.relY, v2.relY);
    const coefficients = matrixVectorMult(inv, [pt.relX , pt.relY]);
    // Round off

    const rounded = coefficients.map((c) => Math.round(c));
    return rounded;
}

The blue shaded area represents the region in which Babai's algorithm will choose the white point as the "closest" point.