Finding pairwise intersections inside a query range

Mark T. de Berg, Joachim Gudmundsson, A. Mehrabi Davoodabadi (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
252 Downloads (Pure)


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⋅polylogn) and with query time O((k+1)⋅polylogn) time, where k is the number of reported pairs, for two classes of objects in R2 : 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 structure of size O(nn−−√⋅polylogn) and query time O((n−−√+k)⋅polylogn) . When the objects and query are fat, we obtain O((k+1)⋅polylogn) query time using O(n⋅polylogn) storage.
Original languageEnglish
Pages (from-to)3253-3269
Number of pages17
Issue number11
Publication statusPublished - 1 Nov 2018


  • Data structures
  • Computational geometry
  • Intersection searching


Dive into the research topics of 'Finding pairwise intersections inside a query range'. Together they form a unique fingerprint.

Cite this