Three-Sided Skyline Counting Queries
Suruchi Kushwaha · 2025
A two-dimensional point p=(p.x,p.y) dominates another point p'=(p'.x,p'.y) if p.x ≥ p'.x and p.y>p'.y or p.x>p'.x and p.y ≥ p'.y. The skyline of a point set P is a subset P' ⊆ P such that every point in P' is not dominated by any other point in P. An orthogonal skyline counting query Q on a set of points P asks for the number of points on the skyline of P ⋂ Q. In this work we study data structures that support orthogonal skyline counting queries in the special case when the query range is bounded on three sides. First, we describe a linear space data structure that counts the points on the skyline of a top-open three-sided query range in O(log log n) time. We also consider a variation of the skyline problem where each of the points have some category, which we call color. An orthogonal color skyline query Q on a set of points P returns the distinct color of points on the skyline of P ⋂ Q. We achieve a solution for top-open three-sided color skyline counting query that requires O(log n/ log log n) time and linear space. Additionally, we show the reduction of four-sided skyline query to a bottom-open three-sided skyline query establishing that solving the skyline problems in a bottom-open three-sided query range is as hard as solving it for a four-sided query range. In contrast, we show that top-open three-sided skyline counting queries can be solved in just O(log log n) time. This demonstrates that for orthogonal skyline queries, although the top-open and bottom-open three-sided query ranges may seem similar, their computational complexities differ significantly.