2015/02/21 by Mark de Berg, de Berg, Mark, Joachim Gudmundsson +3
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1502.06079
arxiv created 2015/02/21 · arxiv updated 2015/02/24
We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q. We present data structures of size O(n(\rm polylog n)) and with query time O((k+1)(\rm polylog n)) time, where k is the number of reported pairs, for two classes of objects in the plane: 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, we present a data structures of size O(n√(n)(\rm polylog n)) and query time O((√(n)+k)(\rm polylog n)). When the objects and query are fat, we obtain O((k+1)(\rm polylog n)) query time using O(n(\rm polylog n)) storage.