Finding a closest point to an n-dimensional plane over lattice

42 Views Asked by At

I have a discrete $n$-dimensional space $\mathbb{Z}^n$, and $x$ is $n$-dimensional point in $\mathbb{Z}^n$, with $$x=[x_1 x_2 ... x_n]^T$$ and $x_i \in \mathbb{Z}$ $\forall i=1, 2, ..., n$.

The problem goes as follows: We have a plane defined by $a_1 x_1+a_2 x_2 + ... +a_n x_n=b$ where $a_i \in R$. Is there a polynomial time algorithm for finding the closest point $x$ to the plane?