TY - CONF T1 - A dynamic data structure for approximate range searching T2 - Proceedings of the 2010 annual symposium on Computational geometry Y1 - 2010 A1 - Mount, Dave A1 - Park,Eunhui KW - Approximation algorithms KW - dynamic data structures KW - geometric data structures KW - quadtrees KW - Range searching AB - In this paper, we introduce a simple, randomized dynamic data structure for storing multidimensional point sets, called a quadtreap. This data structure is a randomized, balanced variant of a quadtree data structure. In particular, it defines a hierarchical decomposition of space into cells, which are based on hyperrectangles of bounded aspect ratio, each of constant combinatorial complexity. It can be viewed as a multidimensional generalization of the treap data structure of Seidel and Aragon. When inserted, points are assigned random priorities, and the tree is restructured through rotations as if the points had been inserted in priority order. In any fixed dimension d, we show it is possible to store a set of n points in a quadtreap of space O(n). The height h of the tree is O(log n) with high probability. It supports point insertion in time O(h). It supports point deletion in worst-case time O(h2) and expected-case time O(h), averaged over the points of the tree. It can answer ε-approximate spherical range counting queries over groups and approximate nearest neighbor queries in time O(h + (1/ε)d-1). JA - Proceedings of the 2010 annual symposium on Computational geometry T3 - SoCG '10 PB - ACM CY - New York, NY, USA SN - 978-1-4503-0016-2 UR - http://doi.acm.org/10.1145/1810959.1811002 M3 - 10.1145/1810959.1811002 ER -