Item

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}^{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 {\em 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 {\em 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).