I/O-efficient dynamic point location in monotone planar subdivisions


Journal Article

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(logB2 N) I/Os (worst-case) and updates in O(logB2 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/BlogM/BN/B)logbN) 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/BlogM/BN/B) logb N) = O(logb2 N) I/Os (amortized) per update, so that reachability queries can be answered in O(logB N) I/Os (worst case).

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Brodal, GS; Vitter, JS

Published Date

  • January 1, 1999

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 11 - 20

Citation Source

  • Scopus