# Optimal Planar Orthogonal Skyline Counting Queries

Technical Report, 1304.7959, arXiv.org, 17 pages, April 2013.

## 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*',*y*')
satisfies *x*'≥ *x* and *y*'≥ *x*. 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*\*c**a**p* *R*. We present a data structure for storing *n* points
with integer coordinates having query time *O*(lg *n*/lglg *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 Ω(lg *n*/lglg *n*).

**Online version**
arxiv1304.7959.pdf (379 Kb), arxiv1304.7959.v1.pdf (376 Kb)

**Links**

**BIBT**_{E}X entry

@techreport{arxiv1304.7959,
author = "Gerth St{\o}lting Brodal and Kasper Green Larsen",
institution = "arXiv.org",
month = "April",
number = "1304.7959",
pages = "17",
title = "Optimal Planar Orthogonal Skyline Counting Queries",
year = "2013"
}