Shortest path and sorting points in a 2-dimensional space

Question

Let's say I have an object in a 2-dimensional space, and a set of points that I need that object to visit. Points may be added at any time, but not removed.

What I want is to be able to determine the next closest point to where my object is in O(lg(n)) time, then go to it, then determine the next closest, etc..

A simple priority queue doesn't work for this because the object is changing position, so the queue would need to be rearranged each time it moves. I was imagining sorting the points into a BST somehow, but I'm unsure of how to sort with respect to (x, y) or if it's even possible.

This feels like I could be trying to solve traveling salesman without realizing it, if so, I apologize haha.

Answer 1

One option would be to use a space partitioning tree like a quadtree or k-d tree to store all of the points in space. These data structures efficiently (usually in sublinear time) support queries of the form "what is the closest points to point p?" You could then do the following:

1. Build a space partitioning tree for the points in space.
2. Use the tree to find the point p closest to your starting point.
3. Repeat the following:
   1. Move to point p.
   2. Remove p from the tree.
   3. Set p to be the point closest to your current location.

Hope this helps!