Donald Bren School of Information and Computer Sciences

Given a set of points in a k-dimensional space, an orthogonal range query is a request for the number of points in a specified k-dimensional box. We present a dynamic data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries. The worst-case time complexity for n operations is 0(n log^k n); the space used is 0(n log^k-1 n) . (0-notation here is with respect to n; the constant is allowed to depend on k.) This is faster than the best previous algorithm by a factor of log n; the data structure also handles deletions in a more general context than previous fast algorithms.