Lower bounds on the complexity of simplex range reporting on a pointer machine

DOI10.1007/3-540-55719-9_95zbMath1425.68430OpenAlexW2098334530MaRDI QIDQ5204338

Burton Rosenberg, Bernard Chazelle

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55719-9_95

zbMATH Keywords

convex hullSteiner minimal treepointer machinequery timepartition tree

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 (2)

Reporting points in halfspaces ⋮ How hard is half-space range searching?

Cites Work

• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Range searching with efficient hierarchical cuttings
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygonal intersection searching
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Quasi-optimal range searching in spaces of finite VC-dimension
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: I. The reporting case
• Filtering Search: A New Approach to Query-Answering
• Point retrieval for polygons
• Polygon Retrieval
• On Heilbronn's Triangle Problem
• A Lower Bound for Heilbronn'S Problem
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Lower bounds on the complexity of simplex range reporting on a pointer machine