A PTAS for $k$-hop MST on the Euclidean plane: Improving Dependency on $k$

For any $epsilon>0$, Laue and Matijevi{c} [CCCG07, IPL08] give a PTAS for finding a $(1+epsilon)$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/epsilon)^{O(k/epsilon)}$. In this paper, we present an algorithm that runs in time $(n/epsilon)^{O(log k cdot(1/epsilon)^2cdotlog^2(1/epsilon))}$. This gives an improvement on the dependency on $k$ on the exponent, while having a worse dependency on $epsilon$. As in Laue and Matijevi{c}, we follow the framework introduced by Arora for Euclidean TSP. Our key ingredients include exponential distance scaling and compression of dynamic programming state tables.