# Shortest hamiltonian path for different dimension points

The shortest Hamiltonian path (solution) for a set of points in $$\mathbb{R}^k$$ (in Euclidean space) changes subject to $$k$$.

For example if for $$k=1$$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $$O(n\log n)$$.

My question is what happens when $$k$$ increases - does the solution become more and more complex or is it the same for all values of $$k$$ larger than $$1$$?

1. For every fixed $$k$$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
2. Trevisan showed that there is no PTAS when $$k = \log n$$ (unless P=NP).
3. Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $$k$$!