2011/06/24 by Meng He, J. Ian Munro, He, Meng +3
Computer Science · #Algorithms and Data Compression #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1106.5076
11 pages (lncs fullpage). This is a corrected version of the preliminary version of the paper that appeared in ISAAC 2011
openalex publication_date 2011/06/24 · arxiv created 2013/05/08 · arxiv updated 2013/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set S of n points in the plane, we consider the problem of answering range selection queries on S: that is, given an arbitrary x-range Q and an integer k > 0, return the k-th smallest y-coordinate from the set of points that have x-coordinates in Q. We present a linear space data structure that maintains a dynamic set of n points in the plane with real coordinates, and supports range selection queries in O((\lg n / \lg \lg n)2) time, as well as insertions and deletions in O((\lg n / \lg \lg n)2) amortized time. The space usage of this data structure is an Θ(\lg n / \lg \lg n) factor improvement over the previous best result, while maintaining asymptotically matching query and update times. We also present a succinct data structure that supports range selection queries on a dynamic array of n values drawn from a bounded universe.