Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
1  
Does the following paper not answer your question: citeseerx.ist.psu.edu/viewdoc/… –  Suvrit Apr 16 '11 at 9:52
    
Thanks, Suvrit, it seems it discusses the question - I will study it. –  Alexander Chervov Apr 16 '11 at 10:03
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
    
Thank You very much! –  Alexander Chervov Apr 16 '11 at 17:12
    
Would you be so kind to look at the continuation of this question: "Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z)" mathoverflow.net/questions/61933/… –  Alexander Chervov Apr 16 '11 at 17:37
add comment

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.

share|improve this answer
    
Thank You very much! –  Alexander Chervov Apr 16 '11 at 17:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.