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