Optimal Planar Orthogonal Skyline Counting Queries

Gerth Stølting Brodal and Kasper Green Larsen

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\cap 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 nlgO(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

BIBTEX 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"
}