Optimal Planar Orthogonal Skyline Counting Queries

The skyline of a set of points in the plane is the subset of maximal points, where a point $(x,y)$ is maximal if no other point $(x^{\mathrm{\prime }},y^{\mathrm{\prime }})$ satisfies $x’\ge x$and$y’\ge Y$\mathrm{.}Weconsidertheproblemofpreprocessingaset$P$of$n$ points into a space efficient static data structure supporting orthogonal skyline counting queries, i.e. given a query rectangle $R$ to report the size of the skyline of $P$ intersected with $R$. We present a data structure for storing n points with integer coordinates having query time $O(\lg n\mathrm{/}\lg \lg n)$ and space usage $O(n)$. The model of computation is a unit cost RAM with logarithmic word size. We prove that these bounds are the best possible by presenting a lower bound in the cell probe model with logarithmic word size: Space usage $n{\lg }^{O(1)}n$ implies worst case query time $\Omega(\lg n/\lg\lg n)$.