I/O-Efficient Dynamic Point Location in Monotone Subdivisions

P. K. Agarwal, L. Arge, G. Brodal, and J. S. Vitter. ``I/O-Efficient Dynamic Point Location in Monotone Subdivisions,'' Proceedings of the 10th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA '99), Baltimore, MD, January 1999.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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^2 N)$I/Os (worst-case) and updates in $O(\log_B^2 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+\frac{b}{B}\log_{M/B} \frac{N}{B})\log_b N)$ I/Os (amortized), $2\leq b\leq 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+\frac{b}{B}\log_{M/B} \frac{N}{B})\log_b N)=O(\log_B^2 N)$ I/Os (amortized) per update, so that reachability queries can be answered in $O(\log_B N)$ I/Os (worst case).