Spanners and Sparsifiers for Graphs on Euclidean Point Sets
December 12, 2018 (GHC 8102)

Consider a graph G obtained from Euclidean point sets by taking the Euclidean distance between points, raised to some power p. In this talk, we show how to construct spanners of such a graph efficiently in low dimension, and show how to find linear size sparsifiers in nearly linear time in the high dimensional setting. The family of graphs G has been considered before for alternate problems, including minimum cost matching, MSTs, and more.