Dynamic range selection in linear space

DOI10.1007/978-3-642-25591-5_18MaRDI QIDQ3104610zbMATH OpenOpenAlexFDO

Authors Meng He, J. Ian Munro, Patrick K. Nicholson

Publication date 16 December 2011

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.5076

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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((lgn/lglgn{)}^2)$ time, as well as insertions and deletions in $O((lgn/lglgn{)}^2)$ amortized time. The space usage of this data structure is an $Theta(lgn/lglgn)$ 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.

Recommendations

• Multidimensional range selection
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Space efficient dynamic orthogonal range reporting
• Space efficient dynamic orthogonal range reporting

Cited in

(13)

• Inverse range selection queries
• Dynamic path queries in linear space
• Linear-space data structures for range mode query in arrays
• A selectable sloppy heap
• Succinct and Implicit Data Structures for Computational Geometry
• Array range queries
• Dynamic range majority data structures
• Multidimensional range selection
• Dynamic 3-sided planar range queries with expected doubly logarithmic time
• Space efficient data structures for dynamic orthogonal range counting
• Improved time and space bounds for dynamic range mode
• Range selection and median: tight cell probe lower bounds and adaptive data structures
• Dynamic deferred data structuring

This page was built for publication: Dynamic range selection in linear space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104610)