#Rectangle Point-Query
We represent a rectangles as a 4-tuple of points corresponding to the rectilinear boundaries. We pre-process these points into a kd-tree then range search.

Algorithm and Running Time

• Preprocessing: Create a kd-tree with \(d=4\) using \(r = \{x_{\min}, x_{\max}, y_{\min}, y_{\max}\}\ \forall r \in R \) as our dimensions: \(O(n\log n)\) time, \(O(n)\) space.
• Query: Perform a range search and report all points in the region defined below: \(O(n^{3/4} + k)\) time.