2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26063 2026-09-23T23:59:14Z ddc:004 open_access

New Results on Three-Sided Skyline Range Counting and Reporting Kushwaha, Suruchi Nekrich, Yakov Data Structures Range Searching Skyline Queries In the orthogonal skyline range counting (resp. reporting) problem we store the set of points P in a data structure so that for any query range Q the number of points (resp. the list of all points) on the skyline of Q∩ P can be found efficiently. In this paper we study two-dimensional range counting and reporting problems in the case when the query range is bounded on three sides. We describe a linear-space data structure that answers top-open three-sided skyline counting queries in O(log log N) time, where N is the number of points stored in the data structure. We also show that bottom-open three-sided skyline counting queries are as difficult as general four-sided queries and any data structure that uses O(Nlog^c N) space for a constant c requires Ω(log N/log log N) time to answer such queries. Next, we turn to skyline color range queries. In this variant of the problem each point in P is assigned a color and we must count (resp. report) the distinct colors of point on the skyline of Q∩ P. We describe an O(N)-space data structure that answers top-open three-sided color counting queries in O(log N/log log N) time. Finally, we study top-open three-sided skyline color reporting in the EM model and describe a data structure that uses linear space and answers queries in O(k/B+1) I/Os where k is the number of colors on the skyline. This is the first external-memory data structure with optimal query cost and space usage for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suruchi Kushwaha and Yakov Nekrich 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.27 urn:nbn:de:0030-drops-260631 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode