2018/01/23 by Eunjin Oh, Oh, Eunjin, Hee-Kap Ahn +1
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1801.07362
The preliminary version appeared in the Proceedings of 28th International Symposium on Algorithms and Computation (ISAAC 2017)
arxiv created 2018/01/23 · arxiv updated 2018/01/24
We consider the following problem: Preprocess a set S of n axis-parallel boxes in ℝd so that given a query of an axis-parallel box in ℝ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(nlog 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+ klog n) query time using O(nlog 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)log2n+klog2n) query time using O(n√ nlog n) space. For a constant d>2, we present a data structure supporting O(n1-δlogd-1 n + k polylog n) query time for any constant 1/d≤δ<1. The size of the data structure is O(nδd - 2δ+ 1log n).