Lower bounds for intersection searching and fractional cascading in higher dimension

DOI10.1145/380752.380818MaRDI QIDQ5175986zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ding Liu, Bernard Chazelle

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.298.7772

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Lower bounds for intersection searching and fractional cascading in higher dimension
• scientific article; zbMATH DE number 3911764
• GENERALIZED INTERSECTION SEARCHING PROBLEMS
• How hard is half-space range searching?
• Space searching for intersecting objects

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(4)

• Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Lower bounds for set intersection queries
• Lower bounds for intersection reporting among flat objects

This page was built for publication: Lower bounds for intersection searching and fractional cascading in higher dimension

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