首页> 外文期刊>Algorithmica >External Memory Planar Point Location with Logarithmic Updates
【24h】

External Memory Planar Point Location with Logarithmic Updates

机译:具有对数更新的外部存储器平面点位置

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

摘要

Point location is an extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log_B N) I/Os and queries can be answered in O(log_B~2 N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(log_B~2 N) I/Os, but only supports insertions in amortized O(log_B~2 N) I/Os. Our structure is also considerably simpler than previous structures.
机译:在内部存储器模型中以及最近在外部存储器模型中,点位置都是一个经过充分研究的问题。在本文中,我们为一般平面细分中的点位置提出了一种I / O有效的动态数据结构。我们的结构使用线性空间来存储N个细分的细分。段的插入和删除可以在摊销的O(log_B N)I / O中执行,而查询可以在最坏的情况下在O(log_B〜2 N)I / O中进行回答。先前最广为人知的线性空间动态结构还回答了O(log_B〜2 N)I / O中的查询,但仅支持在摊销的O(log_B〜2 N)I / O中的插入。我们的结构也比以前的结构简单得多。

著录项

  • 来源
    《Algorithmica》 |2012年第2期|p.457-475|共19页
  • 作者单位

    MADALGO (Center for Massive Data Algorithmics—A Center of the Danish National Research Foundation), Department of Computer Science, Aarhus University, IT Parken, Aabogade 34, 8200 Aarhus N, Denmark;

    MADALGO (Center for Massive Data Algorithmics—A Center of the Danish National Research Foundation), Department of Computer Science, Aarhus University, IT Parken, Aabogade 34, 8200 Aarhus N, Denmark;

    School of Computer Science and Engineering, Seoul National University, 599 Gwanakro,Gwanak-Gu, Seoul 151-744, Republic of Korea;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    planar point location; external memory model; i/o model; vertical ray shooting query; dynamic data structure;

    机译:平面点位置;外部存储模型;I / O模型;垂直射线查询;动态数据结构;

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号