I/O-efficient 2-d orthogonal range skyline and attrition priority queues

DOI10.1016/j.comgeo.2020.101689zbMath1470.68235OpenAlexW3045481965MaRDI QIDQ827322

Casper Kejlberg-Rasmussen, Jeonghun Yoon, Konstantinos Tsakalidis, Kostas Tsichlas, Yufei Tao

Publication date: 7 January 2021

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2020.101689

zbMATH Keywords

computational geometryrange searchingexternal memoryskyline

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (2)

I/O-optimal categorical 3-sided skyline queries ⋮ Two-dimensional range successor in optimal time and almost linear space

Cites Work

• Unnamed Item
• A new approach to the dynamic maintenance of maximal points in a plane
• Maintenance of configurations in the plane
• On the dynamic maintenance of maximal points in the plane
• Worst-case data structures for the priority queue with attrition
• Surpassing the information theoretic bound with fusion trees
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Range Aggregate Maximal Points in the Plane
• Time-space trade-offs for predecessor search
• Dynamic Planar Range Maxima Queries
• Purely functional, real-time deques with catenation
• Optimal Planar Orthogonal Skyline Counting Queries
• On a model of indexability and its bounds for range queries
• Lower bounds for orthogonal range searching: I. The reporting case
• On rectangular visibility
• On Finding the Maxima of a Set of Vectors
• Optimal External Memory Interval Management
• Dynamic Maintenance of Maxima of 2-d Point Sets
• Dynamic Indexability and the Optimality of B-Trees

This page was built for publication: I/O-efficient 2-d orthogonal range skyline and attrition priority queues