A data structure that makes finding close objects easy

Question

I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to tell which reference points are within a fixed distance of it at any point in time. This must be done in an online fashion. There are a very large number of reference points, so iterating through the list is impractical.

This is in many ways similar to a priority queue, but I don’t see any way to adopt that data structure to this context. Every move would require recalculating the distances which appears to require iterating over the entire list of reference points after every move.

Is there a data structure that works for this context? I can allow for a large amount of precomputation if necessary, though the robot’s path isn’t known in advance so I can’t precompute all the relevant distances or something like that. Iterating over the list of reference points can be done during precomputation, just not online because [number of points] * [number of moves] is too large. A solution that is linear in points and sublinear in moves may be feasible, but I would be highly surprised to learn it exists.

I would also be interested in a data structure that tracks the closest waypoint, if that is feasible but the general question is not.

Answer 1

Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees.

It might also be possible to apply ideas from sweep-line algorithms, sweeping outwards radially from the current position of the robot.

Answer 2

You likely want to use some kind of spatial partitioning. Divide your space into, e.g., a square grid. Each grid cell stores a list of the reference points inside it. To get a list of points that are near your robot, then, you just iterate over all the points in the grid cell that contains the robot and any adjacent grid cells that are close enough to be at least partly inside the radius.