An edge quadtree for external memory

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (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.
Originele taal-2Engels
TitelExperimental Algorithms : 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings
RedacteurenV. Bonifaci, C. Demetrescu, A. Marchetti-Speccamela
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-38526-1
StatusGepubliceerd - 2013

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'An edge quadtree for external memory'. Samen vormen ze een unieke vingerafdruk.

Citeer dit