For more details, see the analogous discussion of line segment data on pages 375-377 of Samet, Foundations of Multidimensional and Metric Data Structures, except that the data structure is based on a PMR k-d tree instead of a PMR quadtree.

PMR Rectangle k-d Tree Demo

Instructions

In Insert mode, click and drag to specify a new rectangle, in Delete mode click inside an existing rectangle to remove it from the quadtree. In Search mode click and drag to specify a rectangle. Rectangles in the quadtree that overlap the specified rectangle will be shown.