An optimal dynamic data structure for stabbing-semigroup queries

Pankaj K. Agarwal, Lars Arge, Haim Kaplan, Eyal Molad, Robert E. Tarjan, Ke Yi

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

Let 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.

Original languageEnglish (US)
Pages (from-to)104-127
Number of pages24
JournalSIAM Journal on Computing
Volume41
Issue number1
DOIs
StatePublished - Jun 4 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Dynamic data structures
  • Semigroup queries
  • Stabbing queries

Fingerprint Dive into the research topics of 'An optimal dynamic data structure for stabbing-semigroup queries'. Together they form a unique fingerprint.

  • Cite this