Graph-Based Nearest-Neighbor Search without the Spread

Jeff Giliberti, Sariel Har-Peled, Jonas Sauer +1

Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in ${\Re }^d$, such that one can answer ap…