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

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(logi N) I/OS (worst-case) and updates in O(lo& N) I/OS (amortized). We also propose a new variant of B-trees, called leuelbalanced B-trees, which allow insert, delete, merge, and split operations in O((l+ $ logM,B f) log, N) I/OS (amortized), 2 5 b 2 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 + $10g~,~ $$) log, N) = O(logi N) I/OS (amortized) per update, so that reachability queries can be answered in O(log, N) I/OS (worst case).