Lower bounds for intersection searching and fractional cascading in higher dimension

DOI10.1016/j.jcss.2003.07.003zbMath1073.68089OpenAlexW4253760044WikidataQ29040066 ScholiaQ29040066MaRDI QIDQ1887711

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards optimal two-dimensional indexing for constraint databases
• A class of algorithms which require nonlinear time to maintain disjoint sets
• External-memory algorithms for processing line segments in geographic information systems
• Dynamic fractional cascading
• Fractional cascading. I: A data structuring technique
• Parallel fractional cascading on hypercube multiprocessors
• Ray shooting in polygons using geodesic triangulations
• Optimal cooperative search in fractional cascaded data structures
• Simplex range reporting on a pointer machine
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: I. The reporting case
• A linear algorithm for determining the separation of convex polyhedra
• Filtering Search: A New Approach to Query-Answering
• A Lower Bound on the Complexity of the Union-Split-Find Problem
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Fractional Cascading Revisited

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