What is an efficient way to find a non-colliding rectangle nearest to a location

Question

For a 2D game I am working on, I am using y axis sorting in a simple rectangle-based collision detection. This is working fine, and now I want to find the nearest empty rectangle at a given location with a given size, efficiently. How can I do this? Is there an algorithm?

I could think of a simple brute force grid test (with each grid the size of the empty space we're looking for) but obviously this is slow and not even a complete test.

Answer 1

Consider using quad-trees to store your rectangles. See http://en.wikipedia.org/wiki/Quadtree for more information.