Finding pairwise intersections inside a query range

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)
112 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.
Originele taal-2Engels
Pagina's (van-tot)3253-3269
Aantal pagina's17
Nummer van het tijdschrift11
StatusGepubliceerd - 1 nov 2018


Duik in de onderzoeksthema's van 'Finding pairwise intersections inside a query range'. Samen vormen ze een unieke vingerafdruk.

Citeer dit