Orthogonal Range Reporting in Three and Higher Dimensions

DOI10.1109/FOCS.2009.58MaRDI QIDQ5171171zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Lars Arge, Kasper Larsen

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.58

Mathematics Subject Classification ID

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

Cited in

(10)

• Optimal deterministic shallow cuttings for 3-d dominance ranges
• Finding pairwise intersections inside a query range
• Finding pairwise intersections of rectangles in a query rectangle
• Range minimum query indexes in higher dimensions
• Permuting and batched geometric lower bounds in the I/O model
• Finding pairwise intersections of rectangles in a query rectangle
• I/O-efficient data structures for colored range and prefix reporting
• Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions
• Algorithms and hardness for multidimensional range updates and queries
• Range counting oracles for geometric problems

This page was built for publication: Orthogonal Range Reporting in Three and Higher Dimensions

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