Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals: Proc. 12th International Computer Science Symposium in Russia

Elena Khramtcova, Maarten Löffler

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    We present a data structure to maintain a set of intervals on the real line subject to fast insertions and deletions of the intervals, stabbing queries, and local updates. Intuitively, a local update replaces an interval by another one of roughly the same size and location. We investigate whether local updates can be implemented faster than a deletion followed by an insertion.

    We present the first results for this problem for sets of possibly overlapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, deletions and stabbing queries in time O(logn)O(log⁡n) , and local updates in time O(logn/loglogn)O(log⁡n/log⁡log⁡n) , where n is the number of intervals. We also analyze the dependence on the ply when it is not constant. Our results are adaptive: the times depend on the current ply at the time of each operation.
    Original languageEnglish
    Title of host publicationComputer Science – Theory and Applications
    PublisherSpringer
    ISBN (Electronic)978-3-319-58747-9
    ISBN (Print)978-3-319-58746-2
    DOIs
    Publication statusPublished - 2017

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume10304

    Bibliographical note

    (to appear)

    Keywords

    • CG, DS, QT, IMP

    Fingerprint

    Dive into the research topics of 'Dynamic stabbing queries with sub-logarithmic local updates for overlapping intervals: Proc. 12th International Computer Science Symposium in Russia'. Together they form a unique fingerprint.

    Cite this