CODEWITHSUNDEEP
algorithmmathgraphics
lemiller
lemiller

Reputation: 131

closest lattice point type question

I can't seem to find a solution to this problem. Let's set Z^2 to be the integer lattice in R^2. Given a rational ray (meaning a vector with rational slope), is there a fast method to compute the closest lattice point to this vector in terms of orthogonal distance? Can this method be generalized to a hyperplane in R^n?

Upvotes: 3

Views: 900

Answers (1)

Samuel Hornus
Samuel Hornus

Reputation: 103

Your question does not seem well defined. How do you define the distance to a vector ? If you're asking for the closest distance from the lattice to the line whose direction is a rational vector (as suggested by your generalization) then the answer is zero, thanks to the rationality: your direction is D = (n1/d1, n2/d2). Then, the point (d2*n1, d1*n2) is on the line.

For the smallest non-zero distance :

We can assume that d1=d2=d : D = (n1/d, n2/d) (which you can get by setting e.g. d = d1*d2). Now, the possible distances from the unit-grid lattice to the line are of the form (Z*n1 + Z*n2)/d = (Z*gcd(n1,n2))/d where Z is the set of integers. (This is a consequence of Bézout theorem). So the minimal non zero distance is gcd(n1,n2)/d where gcd(.,.) gives the greatest common divisor of two integers.

Upvotes: 2

Related Questions