TY - JOUR

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

AU - Berg, de, M.T.

AU - Haverkort, H.J.

AU - Thite, S.

AU - Toma, L.

PY - 2010

Y1 - 2010

N2 - 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(logBn) 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 in O(1/g(logBn) + scan (kg)) I/Os for every e>0, where ke is the number of edges of the subdivision within distance ediam(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(logBn) 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.

AB - 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(logBn) 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 in O(1/g(logBn) + scan (kg)) I/Os for every e>0, where ke is the number of edges of the subdivision within distance ediam(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(logBn) 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.

U2 - 10.1016/j.comgeo.2009.11.001

DO - 10.1016/j.comgeo.2009.11.001

M3 - Article

SN - 0925-7721

VL - 43

SP - 493

EP - 513

JO - Computational Geometry

JF - Computational Geometry

IS - 5

ER -