Decomposable searching problems I. Static-to-dynamic transformation
From MaRDI portal
Publication:3911409
DOI10.1016/0196-6774(80)90015-2zbMath0461.68065OpenAlexW1968301997MaRDI 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
lower boundsmodel of computationalgorithm for approximate matchingsdeletion of elementsdesign of data structuresonline data structures
Related Items
An algorithm for handling many relational calculus queries efficiently. ⋮ Iterated nearest neighbors and finding minimal polytopes ⋮ On the existence of weak greedy matching heuristics ⋮ Dynamic layers of maxima with applications to dominating queries ⋮ Dynamic coresets ⋮ Efficient dynamic range searching using data replication ⋮ Dynamic conflict-free colorings in the plane ⋮ Dynamic half-space range reporting and its applications ⋮ Dynamic Euclidean minimum spanning trees and extrema of binary functions ⋮ Fractional cascading. I: A data structuring technique ⋮ Fractional cascading. II: Applications ⋮ Linear-size nonobtuse triangulation of polygons ⋮ Towards an Optimal Method for Dynamic Planar Point Location ⋮ On estimating the complexity of logarithmic decomposition ⋮ Making data structures persistent ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Average case analysis of dynamic geometric optimization ⋮ Efficient splitting and merging algorithms for order decomposable problems ⋮ Topologically sweeping an arrangement ⋮ Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems ⋮ Efficient independent set approximation in unit disk graphs ⋮ Streaming and dynamic algorithms for minimum enclosing balls in high dimensions ⋮ Incremental Voronoi diagrams ⋮ Massively parallel and streaming algorithms for balanced clustering ⋮ Dynamic connectivity in disk graphs ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Optimal partition trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines ⋮ On bounded leg shortest paths problems ⋮ Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds ⋮ Greedy matching on a grid ⋮ An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Core-Sets: Updated Survey ⋮ Coresets for the Nearest-Neighbor Rule ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ Improved Algorithms for Time Decay Streams ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ Approximation algorithms for the unit disk cover problem in 2D and 3D ⋮ Applications of a new space-partitioning technique ⋮ On ray shooting in convex polytopes ⋮ Minimizing the sum of diameters efficiently ⋮ An almost space-optimal streaming algorithm for coresets in fixed dimensions ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maintaining multiple representations of dynamic data structures ⋮ Dynamic graph coloring ⋮ Faster core-set constructions and data-stream algorithms in fixed dimensions ⋮ Learning big (image) data via coresets for dictionaries ⋮ A note on Euclidean near neighbor searching in the plane ⋮ Voronoi diagrams for a moderate-sized point-set in a simple polygon ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Generalizing Geometric Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS ⋮ An incremental reconstruction method for dynamic planar point location ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Coresets for Fuzzy K-Means with Applications ⋮ Point Location in Incremental Planar Subdivisions. ⋮ A dynamic fixed windowing problem ⋮ An application of $m$-ary trees to the design of data structures for geometric searching problems ⋮ A general class of resource tradeoffs ⋮ Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching ⋮ Dynamic data structures for fat objects and their applications ⋮ Lower bounds on the efficiency of transforming static data structures into dynamic structures ⋮ Efficient splitting and merging algorithms for order decomposable problems. ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Dynamic Conflict-Free Colorings in the Plane ⋮ A lower bound to the complexity of Euclidean and rectilinear matching algorithms
