2012/07/10 by Casper Kejlberg-Rasmussen, Kejlberg-Rasmussen, Casper, Konstantinos Tsakalidis +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #E.1 #F.2.2 #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1207.2341
Submitted to SODA 2013
arxiv created 2012/07/10 · openalex publication_date 2012/07/10 · arxiv updated 2012/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present the first fully dynamic worst case I/O-efficient data structures that support planar orthogonal 3-sided range skyline reporting queries in \bigO (log2Bε n + \fractB1-ε) I/Os and updates in \bigO (log2Bε n) I/Os, using \bigO (\fracnB1-ε) blocks of space, for n input planar points, t reported points, and parameter 0 ≤ ε≤ 1. We obtain the result by extending Sundar's priority queues with attrition to support the operations DeleteMin and CatenateAndAttrite in \bigO (1) worst case I/Os, and in \bigO(1/B) amortized I/Os given that a constant number of blocks is already loaded in main memory. Finally, we show that any pointer-based static data structure that supports dominated maxima reporting queries, namely the difficult special case of 4-sided skyline queries, in \bigO(log\bigO(1)n +t) worst case time must occupy Ω(n (log n)/(log log n)) space, by adapting a similar lower bounding argument for planar 4-sided range reporting queries.