= Geometric spanner
{title2=$d_G(u,v)\leq t\|u-v\|$}
{wiki}
A geometric spanner is a <weighted graph> on points in <Euclidean space>, with edge weights equal to their <Euclidean distances>, in which every pair has a <graph path> of <length> at most $t$ times its direct distance. Its <stretch factor> is the largest ratio $d_G(u,v)/\|u-v\|$, where $d_G$ is shortest-path distance. A square's four perimeter edges, without diagonals, give stretch factor $\sqrt2$: adjacent points have ratio one, and diagonal pairs have route <length> $2$ instead of $\sqrt2$. The aim is to retain short routes with fewer edges than a <complete graph>. https://people.scs.carleton.ca/~michiel/encyc_geometric_spanners.pdf[Gudmundsson, Narasimhan and Smid, Geometric Spanners, §1]{ref}.
Back to article page
