Aarhus University Seal

Optimal Planar Orthogonal Skyline Counting Queries

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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).
Original languageEnglish
Title of host publicationAlgorithm Theory – SWAT 2014 : 14th Scandinavian Symposium and Workshops, Denmark. Proceedings
EditorsR. Ravi, Inge Li Gørtz
Number of pages112
PublisherSpringer VS
Publication year2014
ISBN (print)978-3-319-08403-9
ISBN (Electronic)978-3-319-08404-6
Publication statusPublished - 2014
EventScandinavian Symposium and Workshops on Algorithm Theory - Copenhagen, Denmark
Duration: 2 Jul 20144 Jul 2014
Conference number: 14


ConferenceScandinavian Symposium and Workshops on Algorithm Theory
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 81370635