Finding pairwise intersections of rectangles in a query rectangle

Abstract

We consider the following problem: Preprocess a set S of n axis-parallel boxes in R-d so that given a query with 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 logn) 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 + k logn) query time using O(n logn) 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(root n log(2)n + k log(2)n) query time using O(n root nlogn) space. For a fixed dimension d > 2, we present a data structure supporting O(n(1-delta)log(d-1) n +k log(d-1) n) query time for any constant 0 < delta < 1. The size of the data structure is O(n(delta d-28+1)logn). (C) 2019 Elsevier B.V. All rights reserved.