A Randomized Algorithm for Closest-Point Queries
From MaRDI portal
Publication:3796754
DOI10.1137/0217052zbMATH Open0651.68062OpenAlexW2061845601MaRDI QIDQ3796754FDOQ3796754
Authors: Kenneth L. Clarkson 
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
Recommendations
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)
Cited In (54)
- Hitting sets when the shallow cell complexity is small
- A note concerning the closest point pair algorithm.
- Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints
- Linear time algorithms for Euclidean 1-center in \(\mathfrak {R}^d\) with non-linear convex constraints
- The probabilistic method yields deterministic parallel algorithms
- The exact fitting problem in higher dimensions
- On approximate nearest neighbors under \(l_\infty\) norm
- Cutting hyperplane arrangements
- On ray shooting in convex polytopes
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- A practical approach to the 2D incremental nearest-point problem suitable for different point distributions
- On reporting the \(L_1\) metric closest pair in a query rectangle
- A strong lower bound for approximate nearest neighbor searching
- Computing a Closest Point to a Query Hyperplane in Three and Higher Dimensions
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Sparse convex hull coverage
- Approximating nearest neighbor among triangles in convex position
- Dynamic half-space range reporting and its applications
- A deterministic view of random sampling and its use in geometry
- Point location among hyperplanes and unidirectional ray-shooting
- Chromatic nearest neighbor searching: A query sensitive approach
- Relative neighborhood graphs in three dimensions
- Efficient randomized incremental algorithm for the closest pair problem using Leafary trees
- On overlays and minimization diagrams
- An optimal convex hull algorithm in any fixed dimension
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Randomized Data Structures for the Dynamic Closest-Pair Problem
- Vertical decompositions for triangles in 3-space
- Title not available (Why is that?)
- Cutting hyperplanes for divide-and-conquer
- On range searching with semialgebraic sets
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Randomized quickhull
- POSTURE INVARIANT CORRESPONDENCE OF INCOMPLETE TRIANGULAR MANIFOLDS
- Title not available (Why is that?)
- Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
- Point location in zones of \(k\)-flats in arrangements
- Conic nearest neighbor queries and approximate Voronoi diagrams
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- A simple randomized sieve algorithm for the closest-pair problem
- Computing hereditary convex structures
- Ray shooting on triangles in 3-space
- Vertical decomposition of arrangements of hyperplanes in four dimensions
- Euclidean minimum spanning trees and bichromatic closest pairs
- Approximating Minimization Diagrams and Generalized Proximity Search
- Title not available (Why is that?)
- Closest pair and the post office problem for stochastic points
- One-sided epsilon-approximants
- Simplex Range Searching and Its Variants: A Review
- Optimal partition trees
- A new coding-based algorithm for finding closest pair of vectors
- Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
This page was built for publication: A Randomized Algorithm for Closest-Point Queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3796754)
