Redes planas con n - 1 + k aristas (Sparse Spanners, SS (S,k))

Dado un conjunto S de n puntos en el plano y un entero 0 ≤ k < n, el algoritmo SparseSpanner (S,k), construye un grafo G sobre S con n – 1 + k aristas y dilación O (n / k+1) en tiempo O (nlog n).

El algoritmo parte del árbol generador mínimo sobre S, que descompone en piezas dependiendo del valor k. Luego conecta cada par de estas piezas con la arista más corta de la triangulación de Delaunay.