Optimal Planar Orthogonal Skyline Counting Queries

Gerth Stølting Brodal, Kasper Green Larsen

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 cons…