Bernardo, Guillermo deGagie, TravisLadra, SusanaNavarro, GonzaloSeco, Diego2024-07-092023-02G. de Bernardo, T. Gagie, S. Ladra, G. Navarro, and D. Seco, "Faster compressed quadtrees", Journal of Computer and System Sciences, Vol. 131, pp. 86 - 104, Feb. 2023, doi: 10.1016/j.jcss.2022.09.001http://hdl.handle.net/2183/37832©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.jcss.2022.09.001Versión aceptadaAn early partial version of this paper appeared in Proc. of the Data Compression Conference 2015.[Abstract]: 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 O(1) 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.engAtribución-NoComercial-SinDerivadas 3.0 Españahttp://creativecommons.org/licenses/by-nc-nd/3.0/es/Clustered pointsCompact data structuresHeavy-path decompositionQuadtreesRange queriesjournal articleopen access10.1016/j.jcss.2022.09.001