Dynamic Range Selection in Linear Space

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

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$, r…