Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions

DOI10.1016/j.comgeo.2022.101959OpenAlexW3203340671MaRDI QIDQ6159411

Rasmus Killmann, Peyman Afshani

Publication date: 20 June 2023

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

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

zbMATH Keywords

lower boundhigh dimensiondata structureorthogonal range reportingrectangle stabbing

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Simplex range reporting on a pointer machine
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Filtering Search: A New Approach to Query-Answering
• Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
• Orthogonal Range Reporting in Three and Higher Dimensions
• Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ³
• Orthogonal range reporting

This page was built for publication: Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions