Minimum Weight Euclidean t-spanner is NP-Hard

Paz Carmi, Lilach Chaitman-Yerushalmi

Given a set P of points in the plane, an Euclidean t-spanner for P is a geometric graph that preserves the Euclidean distances between every pair of points in P up to a constant fa…