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 ?
Represent rectangle $R^i$ as $[x_m^i,x_M^i]\times[y_m^i,y_M^i]$, then $R^i$ and $R^j$ overlap iff their $x$-range and $y$-range overlap. From there, maintain a sorted list of the $x_{m/M}$ and $y_{m/M}$ values, and loop over your collection of rectangles.
When you process $R^i$, find every other rectangles that overlap its $x$ or $y$ range. If you find an actual overlap with rectangle $R^j$, merge it on the spot $R^i \gets \text{merge}(R^i,R^j)$ and update the sorted list with the new values of $x/y^i_{m/M}$. Continue until $R^i$ does not overlap any of the remaining rectangles. As $R^i$ grows through merges, $x^i_m$ can only decrease so in the worst case you have to compare it to other $x$ values $2N$ times. Likewise for the other bounds. "Processing $R^i$" is overall a linear procedure in $N$ and gives you a rectangle $R^i$ that does not overlap any of the remaining rectangles.
Repeat this "processing" on every rectangle that has not been "processed" yet. If at some point, an overlap with an "already-processed" $R^i$ is created, it should be detected and handled at the creation of that overlap, so in the end there are no overlap remaining. Overall we obtain an $O(N^2)$ complexity, which is hopefully better than "probably $O(N^3)$".
Off-topic.