Lower bounds for intersection searching and fractional cascading in higher dimension
DOI10.1016/J.JCSS.2003.07.003zbMATH Open1073.68089OpenAlexW4253760044WikidataQ29040066 ScholiaQ29040066MaRDI QIDQ1887711FDOQ1887711
Authors: Bernard Chazelle, Ding Liu 
Publication date: 22 November 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.003
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- A class of algorithms which require nonlinear time to maintain disjoint sets
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Filtering Search: A New Approach to Query-Answering
- A linear algorithm for determining the separation of convex polyhedra
- Towards optimal two-dimensional indexing for constraint databases
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic fractional cascading
- Lower bounds for orthogonal range searching: I. The reporting case
- Title not available (Why is that?)
- Fractional cascading. I: A data structuring technique
- Title not available (Why is that?)
- Simplex range reporting on a pointer machine
- Lower Bounds on the Complexity of Polytope Range Searching
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Ray shooting in polygons using geodesic triangulations
- An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- A Lower Bound on the Complexity of the Union-Split-Find Problem
- External-memory algorithms for processing line segments in geographic information systems
- Optimal cooperative search in fractional cascaded data structures
- Parallel fractional cascading on hypercube multiprocessors
- Fractional Cascading Revisited
Cited In (6)
- I/O-efficient 2-d orthogonal range skyline and attrition priority queues
- Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
- Lower bounds for intersection reporting among flat objects
- Lower bounds for intersection searching and fractional cascading in higher dimension
- New upper bounds for generalized intersection searching problems
- Lower bounds for set intersection queries
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 Q1887711)
