2026-07-23T04:54:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8241 2024-03-06T10:41:53Z ddc:004 open_access

Finding Pairwise Intersections of Rectangles in a Query Rectangle Oh, Eunjin Ahn, Hee-Kap Geometric data structures axis-parallel rectangles intersection We consider the following problem: Preprocess a set S of n axis-parallel boxes in \mathbb{R}^d so that given a query of an axis-parallel box Q in \mathbb{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\log n) supporting O(\log 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(\log n\log^* n+ k\log n) query time using O(n\log n) space.There has been no known result for this problem for higher dimensions, except that for d=3, the best known data structure supports O(\sqrt{n}+k\log^2\log^* n) query time using O(n\sqrt {n}\log n) space. For a constant d>2, we present a data structure supporting O(n^{1-\delta}\log^{d-1} n + k \polylog n) query time for any constant 1/d\leq\delta<1.The size of the data structure is O(n^{\delta d}\log n) if 1/d\leq\delta<1/2, or O(n^{\delta d-2\delta+1}) if 1/2\leq \delta<1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh and Hee-Kap Ahn 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.60 urn:nbn:de:0030-drops-82417 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.60 eng https://creativecommons.org/licenses/by/3.0/legalcode