k-ANNS for a dense 3D map of geometric points (Nearest Neighbor Search)

From Algorithm Wiki
Jump to navigation Jump to search


Within a dataset of $n$ points in a dense 3D geometric map, find approximately the $k$ closest points to a specified point.

Related Problems

Generalizations: k Approximate Nearest Neighbors Search

Related: k Nearest Neighbors Search


$n$: number of points in dataset

$k$: number of neighbors to find

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Projected radial search 2013 $O(k)$ $O({1})$ ? Deterministic Time