Multidimensional Searching Problems

DOI10.1137/0205015MaRDI QIDQ4099207zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Cited in

(34)

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

This page was built for publication: Multidimensional Searching Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4099207)