Decomposable searching problems I. Static-to-dynamic transformation

DOI10.1016/0196-6774(80)90015-2zbMath0461.68065MaRDI QIDQ3911409

James B. Saxe, Jon Louis Bentley

Publication date: 1980

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(80)90015-2

zbMATH Keywords

lower bounds; model of computation; algorithm for approximate matchings; deletion of elements; design of data structures; online data structures

Mathematics Subject Classification ID

68P10: Searching and sorting

68N25: Theory of operating systems

Related Items

An application of $m$-ary trees to the design of data structures for geometric searching problems, GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS, Maintaining multiple representations of dynamic data structures, On ray shooting in convex polytopes, An incremental reconstruction method for dynamic planar point location, Dynamic coresets, Greedy matching on a grid, A lower bound to the complexity of Euclidean and rectilinear matching algorithms, On the existence of weak greedy matching heuristics, Fractional cascading. I: A data structuring technique, Fractional cascading. II: Applications, On estimating the complexity of logarithmic decomposition, Making data structures persistent, Topologically sweeping an arrangement, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Applications of a new space-partitioning technique, Minimizing the sum of diameters efficiently, A note on Euclidean near neighbor searching in the plane, Iterated nearest neighbors and finding minimal polytopes, Dynamic Euclidean minimum spanning trees and extrema of binary functions, Output-sensitive results on convex hulls, extreme points, and related problems, A dynamic fixed windowing problem, A general class of resource tradeoffs, Efficient splitting and merging algorithms for order decomposable problems., An algorithm for handling many relational calculus queries efficiently., Dynamic half-space range reporting and its applications, Linear-size nonobtuse triangulation of polygons, Average case analysis of dynamic geometric optimization, Independent set of intersection graphs of convex objects in 2D, Faster core-set constructions and data-stream algorithms in fixed dimensions, Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching, An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions, Lower bounds on the efficiency of transforming static data structures into dynamic structures