1978/10/01 by George S. Lueker · 4 citations
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Arithmetic #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Data Management and Algorithms #Data structure #Discrete mathematics #Linear space #Mathematics #Notation #Range (aeronautics) #Range query (database) #Search engine #Set (abstract data type) #Space (punctuation) #Theoretical computer science #Tree (set theory)
paper · doi:10.1109/sfcs.1978.1
openalex publication_date 1978/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Given a set of points in a d-dimensional space, an orthogonal range query is a request for the number of points in a specified d-dimensional box. We present a data structure and algorithm which enable one to insert and delete points and to perform orthogonal range queries. The worstcase time complexity for n operations is O(n logd n); the space usea is O(n logd-1 n). (O-notation here is with respect to n; the constant is allowed to depend on d.) Next we briefly discuss decision tree bounds on the complexity of orthogonal range queries. We show that a decision tree of height O(dn log n) (Where the implied constant does not depend on d or n) can be constructed to process n operations in d dimensions. This suggests that the standard decision tree model will not provide a useful method for investigating the complexity of such problems.