Faster Compressed Quadtrees
Travis Gagie, Javier I. Gonzalez-Nova, Susana Ladra, Gonzalo Navarro, Diego Seco · 2015
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 quad tree for a point set in terms of the points' clustering. We then describe aqua tree 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.