首页> 外文期刊>Algorithmica >Space Efficient Dynamic Orthogonal Range Reporting
【24h】

Space Efficient Dynamic Orthogonal Range Reporting

机译:空间高效的动态正交范围报告

获取原文
获取原文并翻译 | 示例

摘要

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(logn + k loglog(4n/(k + 1))) and space O(n loglog n), or in time O(logn + k) and space O(n log~ε n) for any ε > 0. Both data structures can be constructed in O(n log n) time and support insert and delete operations in amortized time O(log~2 ft) and O(log n loglog n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427-462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log~(d-1) n + k), update time O(log~d n), and space O(n log~(d-2+ε) n) for any ε > 0. The model of computation used in our paper is a unit cost RAM with word size log n.
机译:在本文中,我们提出了用于正交范围报告的新型空间高效动态数据结构。所描述的数据结构支持在时间O(logn + k loglog(4n /(k + 1)))和空间O(n loglog n)或在时间O(logn + k)和空间O(n log_εn)的任何ε>0。这两种数据结构都可以在O(n log n)的时间内构造,并分别支持摊销时间O(log〜2 ft)和O(log n loglog n)的插入和删除操作。 。这些结果与静态情况下Chazelle的相应空间上限匹配(SIAM J. Comput。17,427-462,1988)。我们还提出了用于d维范围报告的动态数据结构,其搜索时间为O(log〜(d-1)n + k),更新时间O(log〜dn)和空间O(n log〜(d-2) +ε)n)对于任何ε>0。我们的计算模型是单位成本RAM,字大小为log n。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号