Optimal Planar Orthogonal Skyline Counting Queries

Abstract

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^{\prime },y^{\prime })$ satisfies $x^{\prime }\ge x$ and $y^{\prime }\ge Y$. We consider the problem of preprocessing a set $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/\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)$.

Full version of paper appearing in the proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, 2014

References in corpus (2)

• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Unifying the Landscape of Cell-Probe Lower Bounds