de-Berg, Mark and Haverkort, Herman and Thite, Shripad and Toma, Laura (2010) Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions. Computational Geometry, 43 (5). pp. 493-513. ISSN 0925-7721 http://resolver.caltech.edu/CaltechAUTHORS:20100401-141029797
- Published Version
Restricted to Repository administrators only
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100401-141029797
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.
|Additional Information:||© 2009 Elsevier B.V. Received 14 October 2008; revised 31 August 2009; accepted 13 November 2009. Communicated by P. Widmayer. Available online 17 November 2009. M.d.B. and S.T. were supported by the Netherlands’ Organisation for Scientific Research (NWO) under project No. 639.023.301. L.T. was supported by NSF award No. 0728780. The authors thank Sariel Har-Peled for his extensive contributions, and the referees for their comments.|
|Subject Keywords:||Quadtrees; I/O-efficient spatial indexes; Fat triangulations; Low-density subdivisions|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Ruth Sustaita|
|Deposited On:||02 Apr 2010 22:10|
|Last Modified:||26 Dec 2012 11:56|
Repository Staff Only: item control page