# An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries

## Author(s): Agarwal, Pankaj K; Arge, Lars; Kaplan, Haim; Molad, Eyal; Tarjan, Robert E; et al

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr13549
DC FieldValueLanguage
dc.contributor.authorAgarwal, Pankaj K-
dc.contributor.authorArge, Lars-
dc.contributor.authorKaplan, Haim-
dc.contributor.authorTarjan, Robert E-
dc.contributor.authorYi, Ke-
dc.date.accessioned2021-10-08T19:47:30Z-
dc.date.available2021-10-08T19:47:30Z-
dc.date.issued2012-01en_US
dc.identifier.citationAgarwal, Pankaj K, Arge, Lars, Kaplan, Haim, Molad, Eyal, Tarjan, Robert E, Yi, Ke. (2012). An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries. SIAM Journal on Computing, 41 (1), 104 - 127. doi:10.1137/10078791Xen_US
dc.identifier.issn0097-5397-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr13549-
dc.description.abstractLet S be a set of n intervals in ℝ, and let (S,+) be any commutative semigroup. We assign a weight ω(s) ε S to each interval in S. For a point x ε ℝ, let S(x) C S be the set of intervals that contain x. Given a point q ε ℝ, the stabbing-semigroup query asks for computing ΣsεS(q) ω(s). We propose a linear-size dynamic data structure, under the pointer-machine model, that answers queries in worst-case O(log n) time and supports both insertions and deletions of intervals in amortized O(log n) time. It is the first data structure that attains the optimal O(log n) bound for all three operations. Furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in O(log B n) I/Os, where B is the disk block size. For the restricted case of a nested family of intervals (either every pair of intervals is disjoint or one contains the other), we present a simpler solution based on dynamic trees.en_US
dc.format.extent104 - 127en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleAn Optimal Dynamic Data Structure for Stabbing-Semigroup Queriesen_US
dc.typeJournal Articleen_US
dc.identifier.doidoi:10.1137/10078791X-
dc.identifier.eissn1095-7111-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat