A Succinct, Dynamic Data Structure for Proximity Queries on Point Sets.
Prayaag Venkat, David M. Mount · 2014
A data structure is said to be succinct if it uses an amount of space that is close to the information-theoretic lower bound, but still allows for efficient query processing. Quadtrees are among the most widely used data structures for answering queries on point sets in Euclidean space. In this paper we present a succinct quadtree structure. Our data structure can efficiently answer approximate range queries and approximate nearest neighbor queries and supports insertion and deletion of points. 1