Mark McGranaghan '09
IO-efficient edge quadtrees
The quadtree is one of the most widely used data structures for spatial data. It corresponds to a recursive decomposition of the plane into equal-sized quadrants, until each quadrant is "small enough" (usually, until each quadrant contains O(1) points). In this project we have developed a new algorithm for constructing a segment quadtree that works efficiently when the data is very large. Given a set of n non-intersecting segments in the plane, we show how to build a quadtree of O(n) cells in O(sort(m)) IOs, where m is the number of intersections between the input segments and the cells in the quadtree, and sort() is the complexity of sorting in the IO-model of Agarwal and Vitter.
The segment quadtree can be used as a spatial indexing structure to efficiently answer a variety of geometric queries. One example is the segment-segment intersection (spatial join, or map overlay) problem: determine all intersections among two sets of non-intersecting segments. Given the segment quadtrees of the two datasets, the intersections between the sets can be obtained by traversing the quadtrees in O(scan(n + k)) IOs, where n is the size of the two datasets and k is the size of the output.
Initial experiments indicate that the new algorithm performs competitively in practice on real datasets.