Faster Compressed Quadtrees

Travis Gagie, Javier González-Nova, Susana Ladra, Gonzalo Navarro, and Diego Seco

Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first bound the number of nodes in the quadtree for a point set in terms of the points' clustering. We then describe a quadtree data structure that uses O(1) bits per node and supports faster queries than previous structures with this property. Finally, we present experimental evidence that our structure is practical.