Polynomial-time $(k+\epsilon )$-approximation for $k$-coloured Non-crossing Euclidean TSP

Abstract

Given a $k$-coloured point set $P\subseteq {\mathbb{R}}^2$, the $k$-coloured Non-crossing Euclidean Travelling Salesperson Problem (short $k$-ETSP) asks for $k$ non-crossing closed curves, where one curve spans one corresponding colour class, such that the curves are pairwise non-crossing and the sum of their Euclidean lengths is minimised. This problem is NP-hard as $1$-ETSP is the standard Euclidean Travelling Salesperson Problem. We present a polynomial-time $(k+\epsilon )$-approximation for $k$-ETSP.