2026-08-17T02:52:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8843 2024-03-06T10:42:46Z ddc:004 open_access

Succinct Dynamic One-Dimensional Point Reporting El-Zein, Hicham Munro, J. Ian Nekrich, Yakov Succinct Data Structures Range Searching Computational Geometry In this paper we present a succinct data structure for the dynamic one-dimensional range reporting problem. Given an interval [a,b] for some a,b in [m], the range reporting query on an integer set S subseteq [m] asks for all points in S cap [a,b]. We describe a data structure that answers reporting queries in optimal O(k+1) time, where k is the number of points in the answer, and supports updates in O(lg^epsilon m) expected time. Our data structure uses B(n,m) + o(B(n,m)) bits where B(n,m) is the minimum number of bits required to represent a set of size n from a universe of m elements. This is the first dynamic data structure for this problem that uses succinct space and achieves optimal query time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hicham El-Zein and J. Ian Munro and Yakov Nekrich 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.17 urn:nbn:de:0030-drops-88438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.17 eng https://creativecommons.org/licenses/by/3.0/legalcode