Abstract: We study the following problem: preprocess a set of axis-aligned rectangles R into a data structure that allows us to efficiently report all pairs of rectangles from R that intersect inside an axis-aligned query range Q. We present data structures of size O(n log n) and with query time O(k log n + log n log* n), where k denotes the number of answers.
Paper by Mark de Berg, Joachim Gudmundsson, and Ali D. Mehrabi