In Proc. 14th Scandinavian Workshop on Algorithm Theory, volume 8503 of Lecture Notes in Computer Science, pages 98-109. Springer Verlag, Berlin, 2014.
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 nlg^{O(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
Links
Slides
swat14skyline.pdf (683 Kb), swat14skyline.pptx (398 Kb)
BIBT_{E}X 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