I/O-efficient dynamic point location in monotone planar subdivisions
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).
Agarwal, PK; Arge, L; Brodal, GS; Vitter, JS
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page