Fractional cascading. II: Applications
DOI10.1007/BF01840441zbMATH Open0639.68057DBLPjournals/algorithmica/ChazelleG86aOpenAlexW2032605149WikidataQ56039274 ScholiaQ56039274MaRDI QIDQ1099958FDOQ1099958
Authors: Bernard Chazelle, Leonidas Guibas 
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840441
Recommendations
computational geometrybinary searchiterative searchfractional cascadingrange searchB-treedynamization of data structuresmultiple look-up
Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10)
Cites Work
- Title not available (Why is that?)
- Multidimensional divide-and-conquer
- A class of algorithms which require nonlinear time to maintain disjoint sets
- The design of dynamic data structures
- The power of geometric duality
- Priority Search Trees
- Optimal Point Location in a Monotone Subdivision
- Decomposable searching problems I. Static-to-dynamic transformation
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Visibility and intersection problems in plane geometry
- Location of a Point in a Planar Subdivision and Its Applications
- New Data Structures for Orthogonal Range Queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- How to search in history
- Linear space data structures for two types of range search
- Polygonal intersection searching
- Space searching for intersecting objects
- New upper bounds for neighbor searching
- Searching and storing similar lists
Cited In (37)
- Dynamic Trees and Dynamic Point Location
- Two approaches to building time-windowed geometric data structures
- An efficient \(k\) nearest neighbors searching algorithm for a query line.
- The new \(k\)-windows algorithm for improving the \(k\)-means clustering algorithm
- Efficient authenticated data structures for graph connectivity and geometric search problems
- Fractional cascading. I: A data structuring technique
- Polygonal chain approximation: A query based approach
- Investigation of the cumulative diminution process using the Fibonacci method and fractional calculus
- Aggregate-\textsc{Max} top-\(k\) nearest neighbor searching in the \(L_{1}\) plane
- A general approach for cache-oblivious range reporting and approximate range counting
- Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
- New results on binary space partitions in the plane
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Implicitly representing arrangements of lines or segments
- An improved algorithm for incremental DFS tree in undirected graphs
- Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry
- Optimal cooperative search in fractional cascaded data structures
- Ray shooting in polygons using geodesic triangulations
- Partial enclosure range searching
- Dynamic fractional cascading
- Visibility and intersection problems in plane geometry
- Godzilla onions: a skit and applet to explain Euclidean half-plane fractional cascading (media exposition)
- A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
- Counting and reporting red/blue segment intersections
- Algorithms for three-dimensional dominance searching in linear space.
- Efficient algorithms for center problems in cactus networks
- Improved algorithms for placing undesirable facilities
- Fractional cascading simplified
- On \(k\)-sets in arrangements of curves and surfaces
- Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
- The two-center problem of uncertain points on a real line
- Parallel fractional cascading on hypercube multiprocessors
- One-dimensional \(k\)-center on uncertain data
- Fractional Cascading Revisited
- Partitioning arrangements of lines. II: Applications
- Extending range queries and nearest neighbors
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
This page was built for publication: Fractional cascading. II: Applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099958)
