Succinct Indices for Range Queries with applications to Orthogonal Range Maxima

Details Succinct Indices for Range Queries with applications to Orthogonal Range Maxima Succinct Indices for Range Queries with applications to Orthogonal Range Maxima

2012-04-21

arxiv.org/abs/1204.4835v1

Computer Science

Data Structures and Algorithms

To appear in ICALP 2012

Scientific paper

We consider the problem of preprocessing $N$ points in 2D, each endowed with a priority, to answer the following queries: given a axis-parallel rectangle, determine the point with the largest priority in the rectangle. Using the ideas of the \emph{effective entropy} of range maxima queries and \emph{succinct indices} for range maxima queries, we obtain a structure that uses O(N) words and answers the above query in $O(\log N \log \log N)$ time. This is a direct improvement of Chazelle's result from FOCS 1985 for this problem -- Chazelle required $O(N/\epsilon)$ words to answer queries in $O((\log N)^{1+\epsilon})$ time for any constant $\epsilon > 0$.

Affiliated with

Also associated with

No associations

Rating

Succinct Indices for Range Queries with applications to Orthogonal Range Maxima 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 Succinct Indices for Range Queries with applications to Orthogonal Range Maxima, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Indices for Range Queries with applications to Orthogonal Range Maxima will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729523