When implementing collisions among particles, or in many agent-based games, a classic problem is to compute pairwise distance between all couples of particles.
The first algorithm that springs to mind is a couple of nested loops, and that has time-complexity O(n^2).
I was wondering if there was a faster way...I was considering perhaps a quadtree, but the particles are usually moving, and that apparently creates problems :(
So I did a bit more research and I found this: Closest pair of points problem [link]
which has a Planar case, that is very interesting since it should be "solved in O(n log n) time"!
No comments:
Post a Comment