Shortest path and sort points in two-dimensional space

Question

Let's say I have an object in two-dimensional space and a set of points at which I need this object to visit. Points can be added at any time but not deleted.

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

A simple priority queue does not work for this, because the object changes its position, so the queue must be rearranged every time it moves. I imagined somehow sorting points in BST, but I'm not sure how to sort by (x, y) or if it is possible.

It seems to me that I'm trying to solve a traveling salesman without realizing it, if so, I apologize for the haha.

Answer 1

One option would be to use a space partition tree, similar to a quadrant or kd tree, to store all points in space. These data structures efficiently (usually in sublinear time) support queries of the form "what are the closest points to p?" Then you can do the following:

• Create a space partition tree for points in space.
• Use the tree to find the p point closest to the starting point.
• Repeat the following:
  • Move to point p.
  • Remove p from the tree.
  • Set p as the point closest to your current location.

Hope this helps!