Sweep and prune( http://en.wikipedia.org/wiki/Sweep_and_prune http://en.wikipedia.org/wiki/Sweep_and_prune ) is the "minimum sufficient" 2D broadphase algorithm

Sweep and prune( http://en.wikipedia.org/wiki/Sweep_and_prune http://en.wikipedia.org/wiki/Sweep_and_prune ) is the "minimum sufficient" 2D broadphase algorithm, I'm surprised you didn't mention it. You do want some kind of broadphase because an exhaustive check is O(n^2), which means that around 40-50 objects you start to feel the performance plummet like a stone.