Data Structures19 sections · 729 units
Open in Course

2D Interval Problems

Rectangles as interval pairs

A rectangle is two intervals: [x1,x2][x_1, x_2] and [y1,y2][y_1, y_2]. Two rectangles overlap if both their xx-intervals overlap AND their yy-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.