I have a set of axis aligned rectangles. When two rectangles overlap (partly or completely), they can be merged into their common bounding box. This process works recursively.
Detecting all overlaps and using union-find to form groups, which you merge in the end will not work, because the merging of two rectangles covers a larger area and can create new overlaps. (In the figure below, after the two overlapping rectangles have been merged, a new overlap appears.)
As in my case the number of rectangles is moderate (say $N<100$), a brute force solution is usable (try all pairs and if an overlap is found, merge and restart from the beginning). Anyway I would like to reduce the complexity, which is probably $O(N^3)$ in the worst case.
Any suggestion how to improve this ?