Cull sparse 2D objects by bounding box

A quadtree would probably fit your needs perfectly. It is easy and straightforward to implement and performs well for "normal" scenes. When working with none point size objects you simply use there bounding volumes, aabb in your case, and insert them either in the last nod containing the entire bounding volume (be it internal or leaf node) or in all the leaf nodes the bounding volume intersects. You could also use a combination of both but that is probably not very useful.

If you don't want to use a quad tree there are other alternatives like the good old grid structure, the bsp-tree, bounding volume hierarchies or spatial hashing. Or you could probably just iterate all the objects ant test them all if you have lets say less then 20k objects but then I would use bounding spheres instead as the are much cheaper to test. Actually it's usually a good idea to always test spheres first, even if you have an aabb you test the bounding sphere of the aabb before you test the aabb itself.

Ooooh, that was the basic conceptual idea I'd missed. I'd assumed that all objects had to be stored in the leaves of a quadtree. Thanks!