The Unified Segment Tree and its Application to the Rectangle Intersection Problem

In this paper we introduce a variation on the multidi-mensional segment tree, formed by unifying different in-terpretations of the dimensionalities of the levels within the tree. Nodes in the resulting d-dimensional structure can have up to d parents and 2d children. In order to better visualize these relationships we introduce a di-amond representation of the data structure. We show how the relative positions of the nodes within the dia-mond determine the possible intersections between their representative regions. The new data structure adds the capability to detect intersections between rectangles in a segment tree. We use this to solve the “Rectangle Intersection Problem ” with a more straightforward al-gorithm than has been used previously.