Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

Abstract

We present a new I/O-efficient index structure for storing planar subdivisions. This so-called guard-quadtree is a compressed linear quadtree, which is provably efficient for map overlay, point location, and range queries in low-density subdivisions. In particular, we can preprocess a low-density subdivision with n edges, in O(sort(n)) I/Os, to build a guard-quadtree that allows us to: (i) compute the intersections between the edges of two such preprocessed subdivisions in O(scan(n)) I/Os, where n is the total number of edges in the two subdivisions; (ii) answer a single point location query in O(log_B n) I/Os, and k batched point location queries in O(scan(n)+sort(k)) I/Os; and (iii) answer range queries for any constant-complexity query range Q O(1/ε (log_B n) + scan(k_ε))I/Os for every ε>0, where k_ε is the number of edges of the subdivision within distance εdot operatordiam(Q) from Q. For the special case where the subdivision is a fat triangulation, we show how to obtain the same results with an ordinary (uncompressed) linear quadtree, which we call the star-quadtree. The star-quadtree is fully dynamic and needs only O(log_Bn) I/Os per update. Our algorithms and data structures improve on the previous best known bounds for overlaying general subdivisions, both in the number of I/Os and space usage. The constants in the asymptotic bounds are small, which makes our results applicable in practice. Moreover, our algorithms are simpler than previous approaches and almost all of them are cache-oblivious.