Finding Pairwise Intersections Inside a Query Range
Mark de Berg, Joachim Gudmundsson, Ali D. Mehrabi · Algorithmica · 2017
We study the following problem: preprocess a set $$\mathcal {O}$$ of objects into a data structure that allows us to efficiently report all pairs of objects from $$\mathcal {O}$$ that intersect inside an axis-aligned query range $${Q}$$ . We present data structures of size $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ and with query time $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ time, where k is the number of reported pairs, for two classes of objects in $${\mathbb R}^2$$ : axis-aligned rectangles and objects with small union complexity. For the 3-dimensional case where the objects and the query range are axis-aligned boxes in $${\mathbb R}^3$$ , we present a data structure of size $$O(n\sqrt{n}\cdot {{\mathrm{polylog\,}}}n)$$ and query time $$O((\sqrt{n}+k)\cdot {{\mathrm{polylog\,}}}n)$$ . When the objects and query are fat, we obtain $$O((k+1)\cdot {{\mathrm{polylog\,}}}n)$$ query time using $$O(n\cdot {{\mathrm{polylog\,}}}n)$$ storage.