Succinct Indices for Range Queries with applications to Orthogonal Range Maxima

Arash Farzan, J. Ian Munro, Rajeev Raman

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…