[ColinWright]

That point is actually covered in the article:

Merida's hair is made of 100,000 individual elements. "If you know any combinatorics, you know that if you have n objects, you have n² possible collisions," he says, or 10 billion. How can you render so many collisions quickly enough to be usable? You have to create a new spatial data structure that culls extraneous collisions without being too lossy.

So he's saying that naively with n objects there are n² possible collisions, but they have to do clever things - such as you suggest, or even cleverer - to reduce that. Already there. In the article.

But the GGP's point is that there aren't n² possible collisions, there are only n(n-1)/2 if you allow for the symmetries. But is still grows quadratically, and that's the point being made. Quadratic is too fast.