Finding Pairwise Intersections Inside a Query Range

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