Aarhus University Seal / Aarhus Universitets segl

Lars Arge

An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Pankaj K. Agarwal, Department of Computer Science, Duke University
  • ,
  • Lars Arge
  • Haim Kaplan, Department of Computer science, Tel-Aviv university, Israel
  • Eyal Molad, Department of Computer science, Tel-Aviv university, Israel
  • Robert E. Tarjan, Department of Computer Science, Princeton University, United States
  • Ke Yi, Department of Computer Science and Engineering, HKUST, Hong Kong
Let S be a set of n intervals in $\mathbb{R}$, and let $(\mathbf{S}, +)$ be any commutative semigroup. We assign a weight $\omega(s) \in \mathbf{S}$ to each interval in S. For a point $x \in \mathbb{R}$, let $S(x) \subseteq S$ be the set of intervals that contain x. Given a point $q \in \mathbb{R}$, the stabbing-semigroup query asks for computing $\sum_{s \in S(q)} \omega(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
JournalS I A M Journal on Computing
Volume41
Issue1
Pages (from-to)104–127
Number of pages24
ISSN0097-5397
DOIs
Publication statusPublished - 2012

    Research areas

  • dynamic data structures, stabbing queries, semigroup queries

See relations at Aarhus University Citationformats

ID: 52283315