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 . This is a dramatic improvement upon the best previous result due to Chan et al. [CHJ16], who gave a runtime of about For Steiner tree our methods achieve an even better runtime n(log n) (1/ε) O(ddim 2 ) in doubling spaces. For Euclidean space the runtime can be reduced to 2 (1/ε) O(d 2 ) n log n, improving upon the result of Arora [Aro98] in fixed dimension d.