Fractional cascading. I: A data structuring technique
From MaRDI portal
DOI10.1007/BF01840440zbMATH Open0639.68056OpenAlexW2029814178WikidataQ56039273 ScholiaQ56039273MaRDI QIDQ1099957FDOQ1099957
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/bf01840440
Recommendations
computational geometryiterative searchrange queriesfractional cascadingB-treebinary searchesdynamization of data structuresmultiple look-up
Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10)
Cites Work
- The design of dynamic data structures
- Optimal Point Location in a Monotone Subdivision
- Decomposable searching problems I. Static-to-dynamic transformation
- Design and implementation of an efficient priority queue
- Fractional cascading. II: Applications
- Amortized Computational Complexity
- Rectilinear line segment intersection, layered segment trees, and dynamization
- Searching and storing similar lists
Cited In (only showing first 100 items - show all)
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Title not available (Why is that?)
- Dynamic Trees and Dynamic Point Location
- Hidden surface removal for rectangles
- Untangled monotonic chains and adaptive range search
- An algorithm for handling many relational calculus queries efficiently.
- Optimal external memory planar point enclosure
- Parallel computational geometry of rectangles
- Using persistent data structures for adding range restrictions to searching problems
- Towards optimal range medians
- Efficient authenticated data structures for graph connectivity and geometric search problems
- Parallel methods for visibility and shortest-path problems in simple polygons
- Polygonal chain approximation: A query based approach
- Dominance made simple
- Efficient algorithms for the one-dimensional \(k\)-center problem
- Computing on a free tree via complexity-preserving mappings
- Approximating points by a piecewise linear function
- Geometric applications of posets
- The range co-minima problem
- Aggregate-\textsc{Max} top-\(k\) nearest neighbor searching in the \(L_{1}\) plane
- EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION
- Lower bounds for intersection searching and fractional cascading in higher dimension
- Vertical decompositions for triangles in 3-space
- New results on binary space partitions in the plane
- Region-restricted clustering for geographic data mining
- Linear space data structures for two types of range search
- Consecutive interval query and dynamic programming on intervals
- Nearest-neighbor searching under uncertainty. I
- Optimal cooperative search in fractional cascaded data structures
- Ray shooting in polygons using geodesic triangulations
- Dynamic fractional cascading
- Visibility and intersection problems in plane geometry
- Making data structures persistent
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Towards an optimal method for dynamic planar point location
- Line-segment intersection made in-place
- The maximum box problem for moving points in the plane
- Efficient algorithms for center problems in cactus networks
- Improved algorithms for placing undesirable facilities
- The shortest watchtower and related problems for polyhedral terrains
- Searching and storing similar lists
- A note on the \(\epsilon\)-indicator subset selection
- FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING
- Maintaining the minimal distance of a point set in polylogarithmic time
- Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
- Parallel algorithms for the segment dragging problem
- Line-segment intersection reporting in parallel
- Polygonal path simplification with angle constraints
- Hidden surface removal for \(c\)-oriented polyhedra
- Output-sensitive generation of the perspective view of isothetic parallelepipeds
- Output-sensitive generation of the perspective view of isothetic parallelepipeds
- Parallel fractional cascading on hypercube multiprocessors
- Intersection queries in sets of disks
- External-memory algorithms for processing line segments in geographic information systems
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- One-dimensional \(k\)-center on uncertain data
- Intersection queries in sets of disks
- On the two-dimensional Davenport-Schinzel problem
- Efficient geometric-based computation of the string subsequence kernel
- Deferred Data Structuring
- Point location in fat subdivisions
- Homogeneous 2-hop broadcast in 2D
- Fractional cascading. II: Applications
- I/O-efficient dynamic planar point location
- Covering a set of line segments with a few squares
- Dynamic Planar Point Location in External Memory.
- Two approaches to building time-windowed geometric data structures
- Title not available (Why is that?)
- Confluent persistence revisited
- Geometric hitting set for line-constrained disks
- Faster shortest paths in dense distance graphs, with applications
- Point enclosure problem for homothetic polygons
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
- Data structures for range-aggregation over categories
- Range-max queries on uncertain data
- Algorithms for extracting motifs from biological weighted sequences
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
- Geometric applications of posets
- Space-efficient indexes for forbidden extension queries
- Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects
- On the line-separable unit-disk coverage and related problems
- Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
- Sweep methods for parallel computational geometry
- An improved algorithm for incremental DFS tree in undirected graphs
- Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry
- Time windowed data structures for graphs
- Fault tolerant depth first search in undirected graphs: simple yet efficient
- Partial enclosure range searching
- Godzilla onions: a skit and applet to explain Euclidean half-plane fractional cascading (media exposition)
- Cache-oblivious iterated predecessor queries via range coalescing
- A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
- Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
- Counting and reporting red/blue segment intersections
- Space Efficient Multi-dimensional Range Reporting
- Fractional cascading simplified
- External memory fully persistent search trees
- External memory orthogonal range reporting with fast updates
- The two-center problem of uncertain points on a real line
This page was built for publication: Fractional cascading. I: A data structuring technique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099957)
