# Algorithm for enumerating grid points by distance from given point

I'm trying to devise an algorithm for enumerating all points on a 2D grid in order of their Euclidean distance to a given target point. I know I could just get a bunch of them that are close to the target and then sort them, but that's not what I want. I want something that will output every point, out to infinity, in order of their distance to the target.

At the bare minimum, I need something that works if the target point is also a grid point. But ideally, I want something that works for any target, even non-grid points. Ideally ideally, I want something that works for grids of an uneven x-y scale.

• Start as you suggested; take a number of lattice point close to the origin, sort them by distance from the origin, and look for a pattern. For example, sort $\{(x,y)|-10\leq x,y\leq 10\}$ in increasing order of $x^2+y^2$ and see what you get. – saulspatz Aug 16 '18 at 16:49
• Are your out-of-grid points rational (combinations of grid points)? Or some sort of algebraic ones? Or the most complex case of transcendental ones is the one? – metamorphy Aug 16 '18 at 16:50
• Yes, out-of-grid points can be assumed rational – Paul Accisano Aug 16 '18 at 16:52
• Then your way is towards integer quadratic forms. Whatever the actual problem(s) you face... – metamorphy Aug 16 '18 at 17:01

This uses $O(\sqrt n)$ space to print $n$ points, and it takes $O(\log n)$ work to print point number $n$.