A rectangle is two intervals: and . Two rectangles overlap if both their -intervals overlap AND their -intervals overlap.
Common problems:
- Rectangle overlap detection
- Rectangle union area
- Point in rectangle queries
These extend 1D interval tree ideas to 2D. Often solved with sweep line algorithms: sweep in one dimension, use interval tree in the other.