  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',y')$ satisfies $x'\ge
x$ and $y'\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)$.
