Approximate closest-point queries in high dimensions

DOI10.1016/0020-0190(93)90222-UzbMath0795.68187OpenAlexW1998512964MaRDI QIDQ1209329

Marshall W. Bern

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90222-u

zbMATH Keywords

data structurescomputational geometrypattern matchingquadtreesclosest-point queries

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

On Locality-Sensitive Orderings and Their Applications ⋮ A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization ⋮ Approximate range searching in external memory ⋮ Decomposable algorithms for nearest neighbor computing ⋮ SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS ⋮ Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings ⋮ Concurrent linearizable nearest neighbour search in LockFree-kD-tree ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN ⋮ Unnamed Item ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Smallest k-enclosing rectangle revisited ⋮ Chromatic nearest neighbor searching: A query sensitive approach ⋮ Approximate range searching ⋮ On approximate nearest neighbors under \(l_\infty\) norm

Cites Work

• An O(n log n) algorithm for the all-nearest-neighbors problem
• Quad trees: A data structure for retrieval by composite keys
• Optimal Expected-Time Algorithms for Closest Point Problems
• Multidimensional Searching Problems
• An Algorithm for Finding Best Matches in Logarithmic Expected Time