# Simple Collision Detection

Obviously there’s the brute force solution of comparing every dot with every other dot, but a $O(n^2)$ solution will fall over when the number of dots start scaling up. It really feels like a hash table should be possible here, but that kind of lookup only works well on discrete values, not the continuous ranges we’re dealing with here.
Now, obviously there can be any number of dots within these squares, but I was trying to prevent dots from overlapping, which means there can be at most four dots in each square. So there is a constant bound on the number of dots to compare against, and so the problem has been reduced to $O(n)$.