Multidimensional Searching Problems

DOI10.1137/0205015zbMath0333.68031OpenAlexW2067994867WikidataQ56288795 ScholiaQ56288795MaRDI QIDQ4099207

David P. Dobkin, Richard J. Lipton

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0205015

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Search theory (90B40) Pattern recognition, speech recognition (68T10) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

Rooted Uniform Monotone Minimum Spanning Trees, A strong lower bound for approximate nearest neighbor searching, An algorithm for generalized point location and its applications, Optimal randomized incremental construction for guaranteed logarithmic planar point location, Fast spectral analysis for approximate nearest neighbor search, Rough analysis of computation trees, A fast algorithm for point-location in a finite element mesh, Local optimization on graphs, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Time and space complexity of deterministic and nondeterministic decision trees, Moving regular k-gons in contact, Space-efficient functional offline-partially-persistent trees with applications to planar point location, A space-optimal solution of general region location, Dynamic planar point location with optimal query time, Algorithms for high dimensional stabbing problems, Polygonal intersection searching, Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics, Optimal randomized parallel algorithms for computational geometry, The complexity of linear programming, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Approximate closest-point queries in high dimensions, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, A note on a multidimensional searching problem, Learning the tangent space of dynamical instabilities from data, A note on the graph isomorphism counting problem, A note on Euclidean near neighbor searching in the plane, Decision trees based on 1-consequences, Dynamic planar point location with optimal query time, Locating a robot with angle measurements, On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces, A dual approach to detect polyhedral intersections in arbitrary dimensions, New applications of random sampling in computational geometry, Complexity of projected images of convex subdivisions, Stability versus speed in a computable algebraic model