A Randomized Algorithm for Closest-Point Queries
From MaRDI portal
Publication:3796754
DOI10.1137/0217052zbMath0651.68062OpenAlexW2061845601MaRDI QIDQ3796754
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217052
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computing methodologies and applications (68U99)
Related Items
On range searching with semialgebraic sets, Point location among hyperplanes and unidirectional ray-shooting, Ray shooting on triangles in 3-space, A strong lower bound for approximate nearest neighbor searching, The probabilistic method yields deterministic parallel algorithms, Dynamic half-space range reporting and its applications, Vertical decomposition of arrangements of hyperplanes in four dimensions, Vertical decompositions for triangles in 3-space, Point location in zones of \(k\)-flats in arrangements, The exact fitting problem in higher dimensions, Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints, A new coding-based algorithm for finding closest pair of vectors, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Optimal partition trees, Simplex Range Searching and Its Variants: A Review, One-Sided Epsilon-Approximants, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings, Cutting hyperplane arrangements, Euclidean minimum spanning trees and bichromatic closest pairs, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Sparse convex hull coverage, Randomized quickhull, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, On ray shooting in convex polytopes, Relative neighborhood graphs in three dimensions, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Computing hereditary convex structures, Cutting hyperplanes for divide-and-conquer, Conic nearest neighbor queries and approximate Voronoi diagrams, Approximating nearest neighbor among triangles in convex position, POSTURE INVARIANT CORRESPONDENCE OF INCOMPLETE TRIANGULAR MANIFOLDS, Unnamed Item, Unnamed Item, Linear Time Algorithms for Euclidean 1-Center in $$\mathfrak {R}^d$$ with Non-linear Convex Constraints, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem, On overlays and minimization diagrams, A deterministic view of random sampling and its use in geometry, Approximating Minimization Diagrams and Generalized Proximity Search, Chromatic nearest neighbor searching: A query sensitive approach, An optimal convex hull algorithm in any fixed dimension, On approximate nearest neighbors under \(l_\infty\) norm
