Fractional cascading. I: A data structuring technique
From MaRDI portal
Publication:1099957
DOI10.1007/BF01840440zbMath0639.68056OpenAlexW2029814178WikidataQ56039273 ScholiaQ56039273MaRDI QIDQ1099957
Bernard Chazelle, Leonidas J. Guibas
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840440
computational geometryrange queriesiterative searchfractional cascadingB-treebinary searchesdynamization of data structuresmultiple look-up
Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items
An algorithm for handling many relational calculus queries efficiently., Ray shooting in polygons using geodesic triangulations, I/O-efficient dynamic planar point location, Optimal external memory planar point enclosure, Efficient algorithms for center problems in cactus networks, Lower bounds for intersection searching and fractional cascading in higher dimension, Cache-Oblivious Iterated Predecessor Queries via Range Coalescing, Space-efficient indexes for forbidden extension queries, Approximating points by a piecewise linear function, Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric, Fractional cascading simplified, Computing on a free tree via complexity-preserving mappings, DATA STRUCTURES FOR RANGE-AGGREGATION OVER CATEGORIES, Counting and reporting red/blue segment intersections, EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES, Fault tolerant depth first search in undirected graphs: simple yet efficient, On the two-dimensional Davenport-Schinzel problem, Line-segment intersection made in-place, Sweep methods for parallel computational geometry, Optimal cooperative search in fractional cascaded data structures, Vertical decompositions for triangles in 3-space, Towards an Optimal Method for Dynamic Planar Point Location, The shortest watchtower and related problems for polyhedral terrains, New results on binary space partitions in the plane, Making data structures persistent, Space Efficient Multi-dimensional Range Reporting, Nearest-neighbor searching under uncertainty. I, A note on the \(\epsilon\)-indicator subset selection, Geometric Applications of Posets, The homogeneous broadcast problem in narrow and wide strips. I: Algorithms, Consecutive interval query and dynamic programming on intervals, Aggregate-MAX Top-k Nearest Neighbor Searching in the L1 Plane, The maximum box problem for moving points in the plane, Range queries on uncertain data, Geometric hitting set for line-constrained disks, Improved algorithms for placing undesirable facilities, The two-center problem of uncertain points on a real line, Biased range trees, Faster shortest paths in dense distance graphs, with applications, Point enclosure problem for homothetic polygons, Dynamic fractional cascading, Visibility and intersection problems in plane geometry, Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds, Hidden surface removal for rectangles, Parallel algorithms for the segment dragging problem, Using persistent data structures for adding range restrictions to searching problems, Algorithms for extracting motifs from biological weighted sequences, External-memory algorithms for processing line segments in geographic information systems, Parallel computational geometry of rectangles, One-dimensional \(k\)-center on uncertain data, Efficient geometric-based computation of the string subsequence kernel, Efficient algorithms for the one-dimensional \(k\)-center problem, Maintaining the minimal distance of a point set in polylogarithmic time, Range-max queries on uncertain data, Line-segment intersection reporting in parallel, Hidden surface removal for \(c\)-oriented polyhedra, Output-sensitive generation of the perspective view of isothetic parallelepipeds, Parallel fractional cascading on hypercube multiprocessors, Intersection queries in sets of disks, FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING, Parallel methods for visibility and shortest-path problems in simple polygons, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time., Point location in fat subdivisions, Towards optimal range medians, Efficient authenticated data structures for graph connectivity and geometric search problems, Untangled monotonic chains and adaptive range search, Polygonal chain approximation: A query based approach, Output-sensitive generation of the perspective view of isothetic parallelepipeds, Intersection queries in sets of disks, EFFICIENT ALGORITHMS FOR OPTIMIZATION-BASED IMAGE SEGMENTATION, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Dominance made simple, Linear space data structures for two types of range search, Unnamed Item, Region-restricted clustering for geographic data mining, Unnamed Item, Covering uncertain points in a tree, Dynamic Planar Point Location in External Memory., Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model, Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks, Geometric applications of posets, Covering a set of line segments with a few squares, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Partial Enclosure Range Searching, Two approaches to building time-windowed geometric data structures, Homogeneous 2-hop broadcast in 2D, Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane, Dynamic Trees and Dynamic Point Location, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, Time Windowed Data Structures for Graphs, Polygonal path simplification with angle constraints, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, Unnamed Item, Unnamed Item, Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects, Algorithms for bichromatic line-segment problems and polyhedral terrains, Reporting intersecting pairs of convex polytopes in two and three dimensions, The range co-minima problem
Cites Work
- The design of dynamic data structures
- Fractional cascading. II: Applications
- Amortized Computational Complexity
- Optimal Point Location in a Monotone Subdivision
- Searching and storing similar lists
- Decomposable searching problems I. Static-to-dynamic transformation
- Rectilinear line segment intersection, layered segment trees, and dynamization
- Design and implementation of an efficient priority queue
