DOI

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 inves-tigate 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 over-lapping intervals. If the maximum depth of the overlap (a.k.a. ply) is bounded by a constant, our data structure performs insertions, dele-tions and stabbing queries in time O(log n), and local updates in time 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 adap-tive: the times depend on the current ply at the time of each operation.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 12th International Computer Science Symposium in Russia, CSR 2017, Proceedings
РедакторыPascal Weil
ИздательSpringer Nature
Страницы176-190
Число страниц15
ISBN (печатное издание)9783319587462
DOI
СостояниеОпубликовано - 1 янв 2017
Опубликовано для внешнего пользованияДа
Событие12th International Computer Science Symposium in Russia, CSR 2017 - Kazan, Российская Федерация
Продолжительность: 8 июн 201712 июн 2017

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том10304 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция12th International Computer Science Symposium in Russia, CSR 2017
Страна/TерриторияРоссийская Федерация
ГородKazan
Период8/06/1712/06/17

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 38614417