I/O-Efficient Dynamic Point Location in Monotone Subdivisions

Pankaj K. Agarwal, Lars Arge, Gerth Stølting Brodal, and Jeff Vitter

In Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 11-20, 1999.

Abstract

We present an efficient external-memory dynamic data structure for point location in monotone planar subdivisions. Our data structure uses O(N/B) disk blocks to store a monotone subdivision of size N, where B is the size of a disk block. It supports queries in O(log_B² N) I/Os (worst-case) and updates in O(log_B² N) I/Os (amortized).

We also propose a new variant of B-trees, called level-balanced B-trees, which allow insert, delete, merge, and split operations in O((1+(b/B)log_M/B (N/B))log_b N) I/Os (amortized), 2≤ b≤ B/2, even if each node stores a pointer to its parent. Here M is the size of main memory. Besides being essential to our point-location data structure, we believe that level-balanced B-trees are of significant independent interest. They can, for example, be used to dynamically maintain a planar st-graph using O((1+(b/B)log_M/B (N/B))log_b N)=O(log_B² N) I/Os (amortized) per update, so that reachability queries can be answered in O(log_B N) I/Os (worst case).

Copyright notice

Copyright © 1999 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda99.pdf (294 Kb)

DOI

doi.acm.org/10.1145/314500.314525

BIBT_EX entry

@inproceedings{soda99,
  author = "Pankaj K. Agarwal and Lars Arge and Gerth Stølting Brodal and Jeff Vitter",
  booktitle = "Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "doi.acm.org/10.1145/314500.314525",
  isbn = "0-89871-434-6",
  pages = "11-20",
  title = "{I}/{O}-Efficient Dynamic Point Location in Monotone Subdivisions",
  year = "1999"
}