Faster compressed quadtrees (Q2084740)

In geographic information systems (GIS), graphics, and computational geometry querying, storing and processing of two-dimensional points sets is of fundamental importance. In such cases the size of used data structures, measured in machine words, is linear in the number of points. If the points are distributed randomly and uniform over the grid we can use \(O(n \log u)\) bits but there is a possibility to use quadtrees to perform better. Quadtrees are considered as queries of points' coordinates along a root-to-leaf path per point. When the clusters of points are represented, some close points in a cluster share long parts of their common path. When quadtrees are repesented by pointers they overall require \(\Omega(n \log u)\) bits but if it is based on succinct trees paths they use \(O (1)\) bits per quadtree node. In the paper the authors introduce a new space-efficient representation of quadtrees with heavy-path decompositions. Such structures are able to represent a quadtree on \(n\) points using an \(u \times u\) grid with \(O (1)\) bits per quadtree node. It also locates query performance in \(O (\log n)\) time complexity. The paper shows a space analysis of quadtree data structures showing that compressed quadtrees can use \(o(n \log u)\) bits of space on clustered points. The compressed data quadtree structure with heavy-path decomposition with one-step navigation over multiple edges can speed up the query processing. The whole paper is divided into 8 sections. Section 2 explains the theoretical details of compressed quadtree data structures, the next section develops a space analysis of quadtree data structures, whereas Sections 4 and 5 focus on a detailed description of such new structure and present new query algorithms. In Section 6 we have some practical improvements and Section 7 gives results of experiments. The paper is concluded with Section 8.