Optimal Planar Orthogonal Skyline Counting Queries

Gerth Stølting Brodal and Kasper Green Larsen

In Proc. 14th Scandinavian Workshop on Algorithm Theory, volume 8503 of Lecture Notes in Computer Science, pages 98-109. Springer Verlag, Berlin, 2014.

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'≥ 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\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) words. 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 matching 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).

Copyright notice

© Springer International Publishing Switzerland 2014. All rights reserved.

Online version

swat14skyline.pdf (452 Kb)

DOI

10.1007/978-3-319-08404-6_10

Links

Slides

swat14skyline.pdf (683 Kb), swat14skyline.pptx (398 Kb)

BIBTEX entry

@incollection{swat14skyline,
  author = "Gerth St{\o}lting Brodal and Kasper Green Larsen",
  booktitle = "Proc. 14th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/978-3-319-08404-6_10",
  isbn = "0302-9743",
  pages = "98-109",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Optimal Planar Orthogonal Skyline Counting Queries",
  volume = "8503",
  year = "2014"
}

Other versions