1
$\begingroup$

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.

Any ideas on where to start with this?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – saulspatz Aug 16 '18 at 16:49
  • $\begingroup$ 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? $\endgroup$ – metamorphy Aug 16 '18 at 16:50
  • $\begingroup$ Yes, out-of-grid points can be assumed rational $\endgroup$ – Paul Accisano Aug 16 '18 at 16:52
  • $\begingroup$ Then your way is towards integer quadratic forms. Whatever the actual problem(s) you face... $\endgroup$ – metamorphy Aug 16 '18 at 17:01
2
$\begingroup$

Except for the corners of the square your target is in, every grid point has a neighbor that is closer to the target. So you can use a modified breadth-first search:

Maintain a priority queue of points that you have not printed yet but are neighbors to something you have printed, ordered by (squared) distance to the target. Keep taking out the closest point and adding those of its remoter neighbors that are not already in the queue.

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

$\endgroup$
  • $\begingroup$ I was really hoping for something that works in O(1) time, but I think this should suffice.... $\endgroup$ – Paul Accisano Aug 16 '18 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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