Permuting and Batched Geometric Lower Bounds in the I/O Model

DOI10.4230/LIPIcs.ESA.2017.2zbMath1442.68245OpenAlexW2759561597MaRDI QIDQ5111685

Ingo van Duijn, Peyman Afshani

Publication date: 27 May 2020

Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2017.html#AfshaniD17

zbMATH Keywords

lower boundsI/O modelpermutingbatched geometric queries

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• External-memory algorithms for processing line segments in geographic information systems
• The buffer tree: A technique for designing batched external data structures
• Fast permuting on disk arrays
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Algorithms and Data Structures for External Memory
• Lower Bounds for Sorted Geometric Queries in the I/O Model
• I/O-Efficient Range Minima Queries
• On a model of indexability and its bounds for range queries
• Lower bounds for orthogonal range searching: I. The reporting case
• Computational models for parallel computers
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Permuting Information in Idealized Two-Level Storage
• Orthogonal Range Reporting in Three and Higher Dimensions
• Orthogonal range reporting
• Algorithms – ESA 2004

This page was built for publication: Permuting and Batched Geometric Lower Bounds in the I/O Model