For rigid bodies, given reasonably temporally coherent motion between time steps, you can get it down to O(n) with sweep and prune approaches [1]. These might n

For rigid bodies, given reasonably temporally coherent motion between time steps, you can get it down to O(n) with sweep and prune approaches [1]. These might not be the best choice for hair simulation, though. [1] https://en.wikipedia.org/wiki/Sweep_and_prune https://en.wikipedia.org/wiki/Sweep_and_prune