#
Finding Pairwise Intersections Inside a Query Range

##
Nil Mamano

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