The traveling salesman problem for lines, balls and planes

Original · EN

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in Rᵈ, for d≥ 3) or improvements over previous approximations achievable in comparable times (for unit disks in the plane). (I) Given a set of n hyperplanes in Rᵈ, a TSP tour whose length is at most O(1) times the optimal can be computed in O(n) time, when d is constant. (II) Given a set of n lines in Rᵈ, a TSP tour whose length is at most O(³ n) times the optimal can be computed in polynomial time for all d. (III) Given a set of n unit balls in Rᵈ, a TSP tour whose length is at most O(1) times the optimal can be computed in polynomial time, when d is constant.