Home | Bookmarks | Papers | Blog |

Sariel Har-Peled $\newcommand{\Graph}{\mathsf{G}}% \newcommand{\Vertices}{\mathsf{V}}% \newcommand{\Edges}{\mathsf{E}}$

We are given a directed graph $\Graph = (\Vertices,\Edges)$ with $n$ vertices and $m$ edges, with positive weights on the edges, and a parameter $k >0$. We show how to compute for every vertex $v \in \Vertices$, its $k$ nearest neighbors. The algorithm runs in $O( k ( n \log n + m ) )$ time, and follows by a somewhat careful modification of Dijkstra's shortest path algorithm.

This result is probably folklore but since we were unable to find a reference to it, we decided to write it down.

PDF.

Last modified: Wed Apr 1 22:03:18 CDT 2015