What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?

I have a set of rectangles that needed to be grouped based on their locations.
(All the rectangles follow the same orientation.) Two rectangles would be in the same group if the distance between them is less than a certain (constant) threshold.

The obvious algorithm will find all groups in ${O(n^2)}$ time. What I am looking for is an efficient algorithm that can perform better.

Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree. Now for each rectangle $R$, you can determine whether there exist any other rectangles within the prescribed distance, and if so, list them all. Then you can merge all such rectangles into the same group by using a union-find data structure to keep track of which rectangles are in which group. Each rectangle starts out in its own group, and when you find two rectangles that are close to each other (within the prescribed distance), you use the Union operation to merge their two groups.

A number of optimizations are possible. Here is one simple optimization. For each internal node in the quadtree, keep track of a single bit that indicates whether all points (rectangles) in the subtree under that node are known to be in the same group. When enumerating neighbors to $R$, if that bit is set, then you don't need to enumerate all points under that node; it's enough to find any one point (rectangle) under that node, and merge it into the same group as $R$.

StackExchange Computer Science Q#81854, answer score: 4