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.
Cookie Settings
eScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.
Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.
