Yi Zhuang '08
A simple, practical and scalable approach to map overlay
In this project we have developed an experimental evaluation of the IO-efficient quadtree structures proposed by De Berg, Haverkort, Thite and Toma. [http://bowdoin.edu/~ltoma/papers/wads07.pdf] . We describe a few improvements to the algorithms and propose a new structure, the (Guard)-B-quadtree, that extends the ideas behind the Guard-quadtree and has only O(n/B) cells, each with O(B) points, and, if the subdivision has constant density, each cell is intersected by O(B) edges.
We implemented and engineered these structures and present an evaluation of quadtrees and map overlay in external memory using triangulated terrains and the USA TIGER road network. Overall the Star-quadtree and the Guard-B-quadtree are simple and scalable with as little as 128MB of memory. For triangulations, the Star-quadtree is by far the fastest and can process two triangulations totaling 43 million edges in 2.4 hours with 128MB RAM. The algorithms are better in practice than the theoretical worst-case bounds in terms of fatness and density, and perform smoothly even when the input is technically non-fat and has locally narrow triangles and high density.