A range tree for two-dimensional point data where the top level structure is a range tree on the x coordinate value where each non-leaf node also contains a range tree on the y coordinate values of all the points in its subtree. For more details, see pages 14-19 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 80-83 of Samet, Design and Analysis of Spatial Data Structures.
Use Insert and Delete to define a set of points. When done, select Window to create the 2D range tree. In Window mode click and drag to specify a rectangle. All points in this rectangle will be located and displayed.
The animation shows the algorithm's execution. The vertical black lines correspond to the midrange x coordinate values stored in the nonleaf nodes of the tree. Up to four partition levels are shown with the depth of the partition to the immediate left of the vertical line. The thickness of the vertical lines varies with the thickest lines corresponding to the shallowest partition level.