An edge quadtree for external memory

H.J. Haverkort, M. McGranaghan, L. Toma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationExperimental Algorithms : 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings
EditorsV. Bonifaci, C. Demetrescu, A. Marchetti-Speccamela
Place of PublicationBerlin
ISBN (Print)978-3-642-38526-1
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'An edge quadtree for external memory'. Together they form a unique fingerprint.

Cite this