Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model

DOI10.1145/2261250.2261299zbMath1293.68278OpenAlexW2047790048MaRDI QIDQ2874593

Lars Arge, Peyman Afshani, Kasper Green Larsen

Publication date: 7 August 2014

Published in: Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2261250.2261299

zbMATH Keywords

lower boundspointer machineorthogonal range reportingdominance reporting

Mathematics Subject Classification ID

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

Related Items (13)

Finding pairwise intersections of rectangles in a query rectangle ⋮ Dictionary Matching with Uneven Gaps ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions ⋮ Unnamed Item ⋮ Point enclosure problem for homothetic polygons ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Parameterized dictionary matching and recognition with one gap ⋮ Optimal deterministic shallow cuttings for 3-d dominance ranges ⋮ Computing the depth distribution of a set of boxes ⋮ A New Lower Bound for Semigroup Orthogonal Range Searching ⋮ Top tree compression of tries ⋮ Succinct and Implicit Data Structures for Computational Geometry

This page was built for publication: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model