Finding pairwise intersections inside a query range

M.T. Berg, de, J. Gudmundsson, A.D. Mehrabi

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
10 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({\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 R^3, we present a data structures of size $O(n\sqrt{n}({\rm polylog} n))$ and query time $O((\sqrt{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.
Originele taal-2Engels
TitelAlgorithms and Data Structures (14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015)
RedacteurenF. Dehne, J.R. Sack, U. Stege
Plaats van productieCham
ISBN van geprinte versie978-3-319-21839-7
StatusGepubliceerd - 2015

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

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

Citeer dit