Lower bounds on the complexity of simplex range reporting on a pointer machine (extended abstract)

DOI10.1007/3-540-55719-9_95MaRDI QIDQ5204338zbMATH OpenOpenAlexFDO

Authors 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 hullpartition treepointer machinequery timeSteiner minimal tree

Mathematics Subject Classification ID

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

Recommendations

• Simplex range reporting on a pointer machine
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower bounds for orthogonal range searching: I. The reporting case
• Lower Bounds on the Complexity of Polytope Range Searching

Cites work

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

Cited in

(8)

• Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
• Reporting points in halfspaces
• Simplex range reporting on a pointer machine
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
• Lower Bounds on the Complexity of Polytope Range Searching
• scientific article; zbMATH DE number 176163 (Why is no real title available?)
• How hard is half-space range searching?

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

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