Fall 2015: Theory Seminar
ICS, Room 209, 1:00pm
November 13, 2015:

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