scientific article; zbMATH DE number 7375958

DOI10.4230/LIPIcs.ICALP.2018.31zbMath1502.68091arXiv1805.08602MaRDI QIDQ5002701

Timothy M. Chan, Konstantinos Tsakalidis, Yakov Nekrich, Saladi Rahul

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1805.08602

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

pointer machinesgeometric data structuresI/O modelword RAM modelrectangle stabbingorthogonal point location

Mathematics Subject Classification ID

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

Related Items (4)

I/O-optimal categorical 3-sided skyline queries ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions ⋮ Point enclosure problem for homothetic polygons

Cites Work

• Unnamed Item
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
• Time-space trade-offs for predecessor search
• Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
• Unifying the Landscape of Cell-Probe Lower Bounds
• On Dominance Reporting in 3D
• Online Sorted Range Reporting
• Optimal Point Location in a Monotone Subdivision
• Filtering Search: A New Approach to Query-Answering
• Applications of a Planar Separator Theorem
• Optimal Search in Planar Subdivisions
• Two-Dimensional and Three-Dimensional Point Location in Rectangular Subdivisions
• External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates.
• Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry
• Improved Bounds for Orthogonal Point Enclosure Query and Point Location in Orthogonal Subdivisions in ℝ³
• Orthogonal range searching on the RAM, revisited
• Orthogonal range reporting
• I/O-Efficient Point Location in a Set of Rectangles
• I/O-efficient point location using persistent B-trees

This page was built for publication: