Skip to main content
2 of 2
two ` `
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

How to find closest point to restricted lattice on the plane ? ( m*h1 + n*h2, for 0<m,n<N)

Consider finite piece of lattice i.e. points of the form mh1 + nh2, for 0<m,n<N h1, h2 -some vectors. Consider some point "P" on the plane. How to find (m,n) such that mh1 + nh2 is closest to "P" ? I mean what is the simplest method ? Of course we can use brute force search since finite set of points, but may be there is elegant solution ?

The problem is that "lattice reduction" may bring us out the finite set of points...

The problem may be also reformulated like: minimize in int "k" f(k)= (x - (kb mod a))^2 + (y-kh)^2 , for given a,b,h,x,y (which may be assumed integers)

the first term is jumping in "k" because of mod a and this a problem...

Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209