Collision Detection Methods
Our problem is how to efficiently detect collisions of w by h rectangles with bounded width, MaxW and height, MaxH, in a sparse environment containing n cells. We've thought up two ways to detect them.
Pixel Checking
We could create a lookup table for each coordinate, and to detect collisions we would go through each of the wh coordinates the element covers and check for collisions. The complexity for this would O(n*E[w]*E[h]) (where E[x] is the expected value of x over all n cells.)
To update the position of a cell, we would have to remove and add O(wh) list items as well.
The space used would be O(n*E[w]*E[h]) as well.
Sorted Neighbor Checking
In this, for each coordinate x and y (will just use x as an example), we would maintain a skip list of cells indexed by their coordinate. Each cell would contain a reference to its location in that list. To determine whether any other cells impinge upon cell i, we would go back in the list to element j, where x(j) < x(i) - MaxW and forward in the list until x(j) > w(i). The complexity to do this for n cells would be O(n*E[N]) where N is the number of neighbors -- that is, the number of cells within maxW of cell i.
To update the position of the cell we would do a remove and add to the skip list, with expected complexity O(lg n).
The space used would be O(n).
Comparisons
Sorted Neighbor Checking has lower space requirements in all non-trivial cases.
For complexity of collision detection, when E[w]E[h] < E[N], Pixel Checking is better. However, it is highly unlikely the E[N] is > E[w]E[h]. For trivial cases like w=h=5, N would have to be greater than 25. Its unlikely we'll see this level of crowding in most cases. In either case, the difference is negligible.
Updating the position shows a strong winner in Sorted Neighbor Checking. Only in the case where 2(E[w]E[h]) < n is Pixel Checking the best solution here.
Conclusion
Since Sorted Neighbor Checking has lower space complexity and lower update complexity, and in most cases lower collision detection complexity, it is likely the best choice for collision detection.
