Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces

摘要

Miller, Teng, Thurston, and Vavasis proved that every k-nearest neighbor graph (k-NNG) in R~d has a balanced vertex separator of size O(n~(1-1/d)k~(1/d)). Later, Spielman and Teng proved that the Fiedler value - the second smallest eigenvalue of the graph — of the Laplacian matrix of a k-NNG in R~d is at O( 1~(2/d)). In this paper, we extend these two results to nearest neighbor graphs in a metric space with doubling dimension 7 and in nearly-Euclidean spaces. We prove that for every l > 0, each k-NNG in a metric space with doubling dimension γ has a vertex separator of size O(k~2l(32l + 8)~(2γ) log~2 L/S log n + n/l), where L and S are respectively the maximum and minimum distances between any two points in P, and P is the point set that constitutes the metric space. We show how to use the singular value decomposition method to approximate a k-NNG in a nearly-Euclidean space by an Euclidean k-NNG. This approximation enables us to obtain an upper bound on the Fiedler value of the k-NNG in a nearly-Euclidean space.