Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces

AbstractMiller, Teng, Thurston, and Vavasis proved a geometric separator theorem which implies that the k-nearest neighbor graph (k-NNG) of every set of n points in Rd has a balanced vertex separator of size O(n1−1/dk1/d). Spielman and Teng then proved that the Fiedler value — the second smallest eigenvalue of the Laplacian matrix — of the k-NNG of any n points in Rd is O((k/n)2/d). In this paper, we extend these two results to nearest neighbor graphs in a metric space with a finite doubling dimension and in a metric space that is nearly-Euclidean. We prove that for every l>0, if (X,dist) forms a metric space with doubling dimension γ, then the k-NNG of every set P of n points in X has a vertex separator of size O(k2l(64l+8)2γlog2LSlogn+nl), where L and S are, respectively, the maximum and minimum distances between any two points in P. We show how to use the singular value decomposition method to approximate a k-NNG in a nearly-Euclidean space by a Euclidean k-NNG. This approximation enables us to obtain an upper bound on the Fiedler value of k-NNGs in a nearly-Euclidean space