Fractional cascading. II: Applications

DOI10.1007/BF01840441zbMath0639.68057OpenAlexW2032605149WikidataQ56039274 ScholiaQ56039274MaRDI QIDQ1099958

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/bf01840441

zbMATH Keywords

computational geometrybinary searchiterative searchfractional cascadingrange searchB-treedynamization of data structuresmultiple look-up

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

An efficient \(k\) nearest neighbors searching algorithm for a query line., Ray shooting in polygons using geodesic triangulations, Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, Efficient algorithms for center problems in cactus networks, Fractional cascading simplified, Counting and reporting red/blue segment intersections, Fractional cascading. I: A data structuring technique, Optimal cooperative search in fractional cascaded data structures, New results on binary space partitions in the plane, Aggregate-MAX Top-k Nearest Neighbor Searching in the L₁ Plane, Range queries on uncertain data, Improved algorithms for placing undesirable facilities, The two-center problem of uncertain points on a real line, Visibility and intersection problems in plane geometry, Partitioning arrangements of lines. II: Applications, On \(k\)-sets in arrangements of curves and surfaces, Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks, One-dimensional \(k\)-center on uncertain data, Parallel fractional cascading on hypercube multiprocessors, Efficient authenticated data structures for graph connectivity and geometric search problems, Polygonal chain approximation: A query based approach, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, A general approach for cache-oblivious range reporting and approximate range counting, Unnamed Item, Implicitly representing arrangements of lines or segments, Partial Enclosure Range Searching, Two approaches to building time-windowed geometric data structures, Dynamic Trees and Dynamic Point Location, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, Extending range queries and nearest neighbors, Algorithms for three-dimensional dominance searching in linear space., The new \(k\)-windows algorithm for improving the \(k\)-means clustering algorithm

Cites Work

• Unnamed Item
• Multidimensional divide-and-conquer
• Linear space data structures for two types of range search
• A class of algorithms which require nonlinear time to maintain disjoint sets
• The design of dynamic data structures
• Visibility and intersection problems in plane geometry
• The power of geometric duality
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygonal intersection searching
• Priority Search Trees
• New Data Structures for Orthogonal Range Queries
• How to search in history
• New upper bounds for neighbor searching
• Optimal Point Location in a Monotone Subdivision
• Searching and storing similar lists
• Decomposable searching problems I. Static-to-dynamic transformation
• Location of a Point in a Planar Subdivision and Its Applications
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Space searching for intersecting objects