Finding Pairwise Intersections Inside a Query Range

We study the following problem: preprocess a set $$ of objects into a data structure that allows us to efficiently report all pairs of objects from $$ that intersect inside an axis-aligned query range $$ . We present data structures of size $$ and with query time $$ time, where k is the number of reported pairs, for two classes of objects in $$ : 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  $$ , we present a data structure of size $$ and query time $$ . When the objects and query are fat, we obtain $$ query time using $$ storage.