Approximate k-Nearest Neighbor Graph on Moving Points

DOI10.22108/TOC.2022.130533.1943MaRDI QIDQ5045992zbMATH OpenOpenAlexFDO

Authors Zahed Rahmati

Publication date 8 November 2022

Full work available at URL https://doaj.org/article/2083fc3d52ee472dbac8ddb7c661695a

zbMATH Keywords

approximationmoving points\(k\)-nearest neighbor graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1832323
• Graph-based time-space trade-offs for approximate near neighbors
• Approximate nearest neighbor search in metrics of planar graphs
• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
• On nearest-neighbor graphs
• On nearest-neighbor graphs
• Sublinear time approximation of the cost of a metric k-nearest neighbor graph

Cites work

• scientific article; zbMATH DE number 6472653 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A simple, faster method for kinetic proximity problems
• Algorithms for proximity problems in higher dimensions
• An O(n log n) algorithm for the all-nearest-neighbors problem
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Computational geometry. Algorithms and applications.
• Kinetic \(k\)-semi-Yao graph and its applications
• Kinetic and dynamic data structures for closest pair and all nearest neighbors
• Kinetic data structures for all nearest neighbors and closest pair in the plane
• Kinetic pie Delaunay graph and its applications
• Kinetic spanners in \(\mathbb R^{d}\)
• On \(k\)-sets in arrangements of curves and surfaces
• On levels in arrangements of curves, iii
• On levels in arrangements of curves. II: A simple inequality and its consequences
• On levels in arrangements of lines, segments, planes, and triangles

Cited in

(5)

• Kinetic \(k\)-semi-Yao graph and its applications
• Kinetic reverse \(k\)-nearest neighbor problem
• A clustering-based approach to kinetic closest pair
• scientific article; zbMATH DE number 1832323 (Why is no real title available?)
• Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

This page was built for publication: Approximate $k$-Nearest Neighbor Graph on Moving Points

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