| New Data Structures for Orthogonal Range Searching (2000) | |||||||||||||||||
Abstract | |||||||||||||||||
| We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R^3, we achieve query time O(log n + k) using space O(n log 1+" n), where n denotes the number of stored points and k the number of points to be reported. For the range reporting problem on an nn grid, we achieve query time O(log log n + k) using space O(n log" n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n). | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||
Publications citing this publication (1) | |||||||||||||||||
| |||||||||||||||||