hide
Free keywords:
-
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).
