Finding Pairwise Intersections of Rectangles in a Query Rectangle
share
We consider the following problem: Preprocess a set S of n axis-parallel boxes in R^d so that given a query of an axis-parallel box in R^d, the pairs of boxes of S whose intersection intersects the query box can be reported efficiently. For the case that d=2, we present a data structure of size O(n n) supporting O( n+k) query time, where k is the size of the output. This improves the previously best known result by de Berg et al. which requires O( n+ k n) query time using O(n n) space. There has been no result known for this problem for higher dimensions, except that for d=3, the best known data structure supports O(√(n)^2n+k^2n) query time using O(n√(n) n) space. For a constant d>2, we present a data structure supporting O(n^1-δ^d-1 n + k polylog n) query time for any constant 1/d≤δ<1. The size of the data structure is O(n^δ d - 2δ + 1 n).
READ FULL TEXT