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

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)