×

Optimal planar orthogonal skyline counting queries. (English) Zbl 1416.68056

Ravi, R. (ed.) et al., Algorithm theory – SWAT 2014. 14th Scandinavian symposium and workshops, Copenhagen, Denmark, July 2–4, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8503, 110-121 (2014).
Summary: 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^{\prime},y^{\prime})\) satisfies \(x^{\prime} \geq x\) and \(y^{\prime} \geq 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/\lg\lg 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 \(n\lg^{O(1)} n\) implies worst case query time \(\Omega(\lg n/\lg\lg n)\).
For the entire collection see [Zbl 1293.68031].

MSC:

68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI arXiv