首页    期刊浏览 2025年06月10日 星期二
登录注册

文章基本信息

  • 标题:Succinct Dynamic One-Dimensional Point Reporting
  • 作者:Hicham El-Zein ; J. Ian Munro ; Yakov Nekrich
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:101
  • 页码:17:1-17:11
  • DOI:10.4230/LIPIcs.SWAT.2018.17
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Succinct Data Structures; Range Searching; Computational Geometry
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有