We consider the problem of building a quadtree subdivision for a set E of n non-intersecting edges in the plane. Our approach is to first build a quadtree on the vertices corresponding to the endpoints of the edges, and then compute the intersections between E and the cells in the subdivision. For any k¿=¿1, we call a K-quadtree a linear compressed quadtree that has O(n/k) cells with O(k) vertices each, where each cell stores the edges intersecting the cell. We show how to build a K-quadtree in O(sort(n¿+¿l)) i/o’s, where l¿=¿O(n 2/k) is the number of such intersections. The value of k can be chosen to trade off between the number of cells and the size of a cell in the quadtree. We give an empirical evaluation in external memory on triangulated terrains and USA TIGER data. As an application, we consider the problem of map overlay, or finding the pairwise intersections between two sets of edges. Our findings confirm that the K-quadtree is viable for these types of data and its construction is scalable to hundreds of millions of edges.
|Title of host publication||Experimental Algorithms : 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings|
|Editors||V. Bonifaci, C. Demetrescu, A. Marchetti-Speccamela|
|Place of Publication||Berlin|
|Publication status||Published - 2013|
|Name||Lecture Notes in Computer Science|
Haverkort, H. J., McGranaghan, M., & Toma, L. (2013). An edge quadtree for external memory. In V. Bonifaci, C. Demetrescu, & A. Marchetti-Speccamela (Eds.), Experimental Algorithms : 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings (pp. 115-126). (Lecture Notes in Computer Science; Vol. 7933). Berlin: Springer. https://doi.org/10.1007/978-3-642-38527-8_12