Dynamic Range Selection in Linear Space

Details Dynamic Range Selection in Linear Space Dynamic Range Selection in Linear Space

2011-06-24

arxiv.org/abs/1106.5076v2

Computer Science

Computational Geometry

10 pages + 5 page appendix (lncs format)

Scientific paper

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 $\Theta(\lg n / \lg \lg n)$ factor improvement over the previous best result, while maintaining asymptotically matching query and update times. We also present the first succinct data structure that supports range selection queries on a dynamic array of $n$ values drawn from a bounded universe.

Affiliated with

Also associated with

No associations

Rating

Dynamic Range Selection in Linear Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamic Range Selection in Linear Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Range Selection in Linear Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-144577