|
Title |
Faster Compressed Quadtrees |
|
Authors |
Guillermo de Bernardo, Travis Gagie, Susana Ladra, Gonzalo Navarro, Diego Seco |
|
Publication date |
2023 |
|
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. |
|
Pages |
86-104 |
|
Volume |
131 |
|
Journal name |
Journal of Computer and System Sciences |
|
Publisher |
Elsevier Science (Amsterdam, The Netherlands) |
|
Reference URL |
|
