Overlap in multiple dimensions is simply the AND of overlap in each dimension. The 3D case comes up in collision detection. For collision detection in games,

Overlap in multiple dimensions is simply the AND of overlap in each dimension. The 3D case comes up in collision detection. For collision detection in games, the objects are usually kept in a sorted order, with separate lists for X, Y and Z. Amusingly, a bubble sort is useful, because, as objects move, they tend to move locally, so a bubble sort quickly restores the order. The sorting algorithm should terminate quickly when there are few or no changes. First seen in I-Collide, 1995. When objects are moving slowly, speed is slightly worse than O(N), but degrades if there's too much motion. 2D sorting speeds things up. If you sort the intervals by start X, start Y, you can process the intervals sequentially. Here's something of mine which does that.[1] A MySQL database does the sort, then feeds the data to this algorithm. Overlaps are detected, sets of overlapping objects are merged, and the sets of overlapping 2D rectangles are emitted. Sort is O(N log N) as usual, and overlap detection is O(N). [1] https://github.com/John-Nagle/maptools/blob/main/rust/src/generator/vizgroup.rs https://github.com/John-Nagle/maptools/blob/main/rust/src/ge...