Finding Pairwise Intersections Inside a Query Range.

We study the following problem: preprocess a set O<inline-graphic></inline-graphic> of objects into a data structure that allows us to efficiently report all pairs of objects from O<inline-graphic></inline-graphic> that intersect inside an axis-aligned query range Q<inline-graphic></inline-graphic>. We present data structures of size O(n·polylogn)<inline-graphic></inline-graphic> and with query time O((k+1)·polylogn)<inline-graphic></inline-graphic> time, where k is the number of reported pairs, for two classes of objects in R2<inline-graphic></inline-graphic>: 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 R3<inline-graphic></inline-graphic>, we present a data structure of size O(nn·polylogn)<inline-graphic></inline-graphic> and query time O((n+k)·polylogn)<inline-graphic></inline-graphic>. When the objects and query are fat, we obtain O((k+1)·polylogn)<inline-graphic></inline-graphic> query time using O(n·polylogn)<inline-graphic></inline-graphic> storage. [ABSTRACT FROM AUTHOR]