Finding overlaps between two lists of axis-aligned rectangles
Dec. 10, 2018

The simple answer is to use a 2-d segment tree.



Given that we have low value for dimension (i.e. two), an appropriate approach would be to use a 2-d segment tree. We use what is known as stabbing query or intersection query. Let list one be the list that is smaller. Store all rectangles from list one in such a tree. Query using rectangles from list two. Time to construct and query are \$O(n_1 \cdot \log^2(n_1))\$ and \$O(\log^2(n_1) \cdot k)\$, respectively, s.t. \$k\$ is number of matches to report. If we use fractional cascading and interval tree, times become \$O(n_1 \cdot \log(n_1))\$ and \$O(\log(n_1) \cdot k)\$, respectively. Assuming these better times, time for all queries is \$O(\textrm{max}(n_2, k_\textrm{overall}) \cdot \log(n_1))\$. Overall time becomes \$O((\textrm{max}(n_2, k_\textrm{overall}) + n_1) \cdot \log(n_1))\$. Given that \$k_\textrm{overall}\$ is in \$O(n_1 \cdot n_2)\$, time could be loosely \$O((n_1 \cdot n_2) \cdot \log(n_1))\$.

If rectangles are not axis-aligned, one might wish to have bounding boxes and then use a tree. In principle we then could use a segment tree again, but a natural alternative (though we usually do not have good guaranteed theoretical running time for it unless we use "look-ahead") could be an R-tree.