Concurrent range reporting in two-dimensional space

DOI10.1137/1.9781611973402.73MaRDI QIDQ5384035zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Cheng Sheng, Yufei Tao, Bryan T. Wilkinson

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/f6bc15915222ae7f0fd2698a78f99392b791358a

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the difficulty of range searching.
• Orthogonal range searching in linear and almost-linear space
• Orthogonal range reporting, query lower bounds, optimal structures in 3-d, and higher-dimensional improvements
• Fully Dynamic Orthogonal Range Reporting on RAM
• Dynamic orthogonal range searching on the RAM, revisited

Cited in

(6)

• Simplex range reporting on a pointer machine
• Two-dimensional range diameter queries
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
• Shared-constraint range reporting
• Four-dimensional dominance range reporting in linear space
• Convexity helps iterated search in 3D

This page was built for publication: Concurrent range reporting in two-dimensional space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384035)