Page "Interval tree" Paragraph 25

First, a range tree in N dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region R. Once the corresponding ranges are found, the only thing that is left are those ranges that enclose the region in some dimension.

To find these overlaps, N interval trees are created, and one axis intersecting R is queried for each.

For example, in two dimensions, the bottom of the square R ( or any other horizontal line intersecting R ) would be queried against the interval tree constructed for the horizontal axis.

Likewise, the left ( or any other vertical line intersecting R ) would be queried against the interval tree constructed on the vertical axis.