Question

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). What are the algorithms to find some nearest lattice point to "P" ?

"Nearest" - means in the sense of the standard Eucleadian distance.

Lattice - means the standard thing - takes some vectors h_1 ... h_n and consider all their combinatioons with INTEGER coefficients. (Let us assume that h_i are independent and their number is exactly the dimension of the ambient R^n).

I think this should pretty well-studied question... Can someone recommend some good literature for it ? What are the general results known for it ? What are the algorithm complexity ? Is it NP problem ?

Answer 1

This problem is often called the "closest vector problem" for lattices (especially by people in theoretical computer science). The real issue is what sort of lattice you have. For example, for the integer lattice $\mathbb{Z}^n$ the problem is easy, and it's not too hard to do it for other famous lattices, for example root lattices. So if you have a specific, not very complicated lattice in mind, you shouldn't necessarily despair.

However, for an arbitrary lattice it's hard. The strongest result I know of offhand is that Dinur, Kindler, Raz, and Safra proved that it is NP-hard to approximate the distance to the closest lattice point by a factor of $n^{c/\log \log n}$ in $n$ dimensions (Combinatorica 23 (2003), 205–243); however, it may have been slightly improved since then. Using LLL lattice basis reduction, you can get an approximation to within a slightly subexponential factor in polynomial time.

For a good overview, see the book Complexity of lattice problems: a cryptographic perspective by Micciancio and Goldwasser.

Answer 2

My guess is that this is going to be hard to solve in reasonable time if you have a large number of dimensions (thousands or more), and don't exploit any particular 'nice' features your lattice might have.

However, I believe it is in NP. The following, while probably impractical, should in theory do what you are asking:

1) Find a reduced lattice basis (LLL algorithm)

2) Use the reduced basis to enumerate all lattice points within a sufficiently large box encompassing the point "P".

3) Compute the Voronoi diagram of this set of points. (Bowyer-Watson algorithm)

You should then be able to find the nearest lattice point by inspection of the Voronoi diagram. If you really need to compute this sort of thing, the trick would be to see if you can avoid step 1) completely, and integrate steps 2) and 3). Otherwise, simply storing the Voronoi diagram will use an explosive amount of memory.