Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

We give an algorithm that computes a (1+ε)-approximate Steiner forest in near-linear time n · 2^(1/ε)O(ddim2) (log log n)2. This is a dramatic improvement upon the best previous result due to Chan et al., who gave a runtime of n^2O(ddim) · 2^(ddim/ε)O(ddim) √log n. For Steiner tree our methods achieve an even better runtime n (log n)^(1/ε)O(ddim2) in doubling spaces. For Euclidean space the runtime can be reduced to 2^(1/ε)O(d2) n log n, improving upon the result of Arora in fixed dimension d.