2012/04/21 by Arash Farzan, J. Ian Munro, Farzan, Arash +3
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1204.4835
openalex publication_date 2012/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of preprocessing N points in 2D, each endowed with\na priority, to answer the following queries: given a axis-parallel rectangle,\ndetermine the point with the largest priority in the rectangle. Using the ideas\nof the \effective entropy of range maxima queries and \succinct\nindices for range maxima queries, we obtain a structure that uses O(N) words\nand answers the above query in O(\log N \log \log N) time. This is a direct\nimprovement of Chazelle's result from FOCS 1985 for this problem -- Chazelle\nrequired O(N/\ε) words to answer queries in O((\log N)1+\ε)\ntime for any constant \ε > 0.\n