Polynomial-time $(k+ε)$-approximation for $k$-coloured Non-crossing Euclidean TSP
2026-07-27 • Computational Geometry
Computational GeometryDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study a problem where you have groups of points each assigned a color, and you want to draw one loop around each color group that doesn't cross any other loops, while keeping the total length of all loops as short as possible. This problem is hard to solve exactly because it generalizes the famous Traveling Salesperson Problem. The authors provide an algorithm that can find a solution within a factor of roughly k (the number of colors) plus a small extra margin, and it runs in polynomial time, meaning it is efficient for use on larger inputs. Their work extends approximation methods to this more complex multicolored setting.
Euclidean Travelling Salesperson ProblemNon-crossing curvesk-coloured point setApproximation algorithmNP-hardPolynomial-timeComputational geometryClosed curveOptimizationEuclidean length
Authors
Daniel Bauer, Jan-Henrik Haunert
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+ε)$-approximation for $k$-ETSP.