2
$\begingroup$

I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:

Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of the points, where the distance is at most $C$.

Note that our list of points is unsorted, and that each point is an actual object so I could give it any property I want.

Now this can easily be done in $O(n^2)$ time, it is also the easiest and not really an issue. However, the time it takes when a new point is added or a point is removed is also $O(n^2)$, and I would like to get that down, because this is done during gameplay (while the initial step is only done at start).

Does anyone know a possible improvement over the simple 'bruteforce'? I tried sorting, twice, and keeping it up to date (using a 4x linked list (up, down, left, right)) but that did not seem to work.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Can you clarify what "where the distance is at most C" means? Does that mean that you are only interested in the nearest neighbor to a point $p_i$ if the distance is $\le C$, otherwise you want it to output "no neighbor near enough"? Are you most interested in practical algorithms, or in something with provable worst-case running time? $\endgroup$ – D.W. May 19 '17 at 18:07
  • $\begingroup$ Thanks! I am only interested if there is a neighbor within distance C of a point. I want it practical. $\endgroup$ – Rahkiin May 19 '17 at 18:46
  • $\begingroup$ OK, cool. Then my answer should take care of that. $\endgroup$ – D.W. May 19 '17 at 18:49
  • $\begingroup$ With your brute-force approach, adding a point takes $O(n)$ time, not $O(n^2)$ time, as you only need to compare the new point to all pre-existing points (there's no need to recompute the distance between two pre-existing points). Deleting a point also takes only $O(n)$ time, not $O(n^2)$ time: there is no need to recompute all pairs of distances, to delte point $x$ you only need to look up the nearest neighbor $y$ and update $y$'s nearest neighbor (by comparing $y$ to all other points). $\endgroup$ – D.W. May 19 '17 at 19:04
  • $\begingroup$ With the bruteforce solution i had: storing only the nearest + distance, for all points the new nearest had to be found as well. So I guess what I now found is just a better bruteforce. $\endgroup$ – Rahkiin May 19 '17 at 19:08
1
$\begingroup$

You want a data structure that supports nearest neighbor search in 2D. There are many options, but a simple one that is widely used for practical situations is a quadtree data structure. It supports both efficient lookup and efficient insert operations.

$\endgroup$
  • $\begingroup$ The mod is in LUA and I think quadtrees might make the implementation much more complicated than necessary, so for my case I think my answer might be best. For others, use quad trees. (not sure what to mark as the answer) $\endgroup$ – Rahkiin May 19 '17 at 18:57
  • $\begingroup$ @Rahkiin, I wouldn't expect the programming language to make a major difference here; it's just a constant factor. Sophisticated data structures are harder to implement than simpler data structures, but if you want an efficient solution that's often necessary. If you want to optimize for ease of implementation, use a linked list and pairwise comparisons and accept that it won't be as fast as other options. Your question made it sound like you wanted to speed up running time. If so, quadtrees (or similar data structures) should provide substantial speedups, especially when $n$ is large. $\endgroup$ – D.W. May 19 '17 at 19:06
0
$\begingroup$

After I linked this to a friend, he found this solution:

Store for every point all other points that are in distance $C$ in a hashmap with the key as the node. (This is $O(n^2)$ with amortized $O(1)$ for hash put) When adding a node $x$, search all nodes and add every node with distance less than $C$ to the list of $x$. Add $x$ to all nodes in the list of $x$ ($O(n + some)$) When removing a node $y$, remove $y$ from the lists of the nodes in the list of $y$. $O(some)$

I tried this quickly in Processing (java-ish) to see if it works, and it seems to have a bit slower initial step, but removing and adding a node is almost no-time.

$\endgroup$
  • $\begingroup$ This looks identical to the brute-force solution described in your question: you do $O(n^2)$ work to construct the data structure, and $O(n)$ work per insertion or deletion, same as the approach in your question. I don't see how the hashtable helps or is relevant here. This will likely be considerably slower than a quadtree or other nearest neighbor data structure, when $n$ is large. $\endgroup$ – D.W. May 19 '17 at 19:02
  • $\begingroup$ True, but $n$ is max 8000. $\endgroup$ – Rahkiin May 19 '17 at 19:06

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.