Editing Interval tree (section)

=== Higher dimensions ===

The interval tree data structure can be generalized to a higher dimension <math>N</math> with identical query and construction time and <math>O(n \log n)</math> space.

First, a [[range tree]] in <math>N</math> dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region <math>R</math>. 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,  <math>N</math> interval trees are created, and one axis intersecting <math>R</math> is queried for each. For example, in two dimensions, the bottom of the square  <math>R</math> (or any other horizontal line intersecting <math>R</math>) would be queried against the interval tree constructed for the horizontal axis. Likewise, the left (or any other vertical line intersecting <math>R</math>) would be queried against the interval tree constructed on the vertical axis.

Each interval tree also needs an addition for higher dimensions. At each node we traverse in the tree, <math>x</math> is compared with  <math>S_{\textrm {center}}</math> to find overlaps. Instead of two sorted lists of points as was used in the one-dimensional case, a range tree is constructed. This allows efficient retrieval of all points in  <math>S_{\textrm {center}}</math> that overlap region <math>R</math>.