2014/11/11 by de Bernardo, Guillermo, Gagie, Travis, Ladra, Susana +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1411.2785
Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using \Oh1 bits per node can break this bound on clustered point sets, while offering efficient range searches. We then describe a new compact quadtree representation based on heavy path decompositions, which supports queries faster than previous compact structures. We present experimental evidence showing that our structure is competitive in practice.