Saturday, November 30, 2013

Pairwise Distance

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