Finding pairwise intersections of rectangles in a query rectangle
Eunjin Oh, Hee-Kap Ahn · Computational Geometry · 2019
We consider the following problem: Preprocess a set S of n axis-parallel boxes in Rd so that given a query with an axis-parallel box in Rd, 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(nlogn) supporting O(logn+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(logn+klogn) query time using O(nlogn) 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(nlog2n+klog2n) query time using O(nnlogn) space. For a fixed dimension d>2, we present a data structure supporting O(n1−δlogd−1n+klogd−1n) query time for any constant 0<δ<1. The size of the data structure is O(nδd−2δ+1logn).