Complexity of the Euclidean TSP with neighborhoods: optimal tours for rays in the plane and approximation for lines in 3-dimensional space

The Euclidean TSP with neighborhoods (TSPN) asks for a shortest tour visiting at least one point of each of a family of input regions. For one-dimensional neighborhoods the complexity map has two conspicuous holes, both explicitly posed as open problems in Dumitrescu's 2012 study of lines and rays in the plane and both unresolved as of August 2026. First, for neighborhoods that are rays (half-lines) in the plane, no polynomial-time algorithm computing an optimal tour or path is known, and the problem is not known to be NP-hard; it interpolates between the polynomial-time solvable case of lines and the NP-hard case of segments, a claimed 2021 resolution was refuted by a published counterexample, and a 2025 exact algorithm for the segment case is only asserted, not proven, to extend to rays. Second, for lines in 3-dimensional space the problem is APX-hard yet admits only polylogarithmic approximation guarantees, and the existence of a polynomial-time constant-factor approximation is the question the literature itself names as the most important open one. The problem asks to settle both: the exact complexity (P versus NP-hard) of optimal tours and paths for planar rays, and the constant-factor approximability of TSPN for lines in $\mathbb{R}^3$.

Background

In the Euclidean traveling salesman problem (TSP) one seeks a shortest closed curve (a tour) through a given set of points; in the path variant one seeks a shortest curve with free endpoints visiting all points. Arkin and Hassin (1994) introduced the TSP with neighborhoods (TSPN): each input point is replaced by a region, and the tour (or path) must visit at least one point of every region. TSPN is markedly harder than point TSP: while the Euclidean TSP admits a polynomial-time approximation scheme (PTAS, an algorithm producing a $(1+\varepsilon)$-approximate solution in polynomial time for every fixed $\varepsilon>0$), TSPN is APX-hard in general, meaning no PTAS exists unless $P=NP$ (de Berg, Gudmundsson, Katz, Levcopoulos, Overmars and van der Stappen, 2005). This motivates classifying the complexity of TSPN by the shape of the allowed neighborhoods.

For unbounded one-dimensional neighborhoods the picture is curiously incomplete. When the neighborhoods are straight lines in the plane, an optimal tour can be computed in polynomial time (Jonsson, 2002) — a tour reflecting off the lines in slope order is optimal, realized as the boundary of a convex polygon. When the neighborhoods are line segments, computing an optimal tour is NP-hard. Rays — half-lines with a single endpoint, infinite in the other direction — lie strictly between: their unbounded direction behaves like a line, while their endpoint behaves like a segment endpoint. Dumitrescu (2012) gave linear-time constant-factor approximation algorithms for lines and rays (tours at most 1.28 times optimal for both, paths at most 1.42 and 2.24 times optimal, respectively), but left open the exact complexity of the ray case and the approximability of the case of lines in three dimensions.

Two structural facts frame the two-dimensional question. First, for neighborhoods that are lines or rays, an optimal TSPN tour is always the boundary of a convex polygon: the perimeter of the convex hull of any closed curve is at most the length of the curve, and the boundary of a convex set intersecting a ray must itself intersect the ray (Antoniadis, de Berg, Kisfaludi-Bak and Skarlatos, 2025). Hence computing a shortest tour for rays equals computing a minimum-perimeter intersecting polygon — a convex polygon of smallest perimeter touching every input object. Second, for segment inputs this minimum-perimeter intersecting polygon problem was recently solved exactly in $O(n^9 \log n)$ time by a dynamic program (Antoniadis et al., 2025); the same paper shows that the one claimed polynomial-time algorithm for rays, due to Tan (2021), rests on a lemma that fails on an explicit counterexample.

In three dimensions, the state of the art for line neighborhoods is: an $O(\log^3 n)$-approximation in polynomial time, obtained by reduction to the group Steiner tree problem (a generalization of Steiner tree in which terminals come in groups and the tree must connect at least one terminal per group; Dumitrescu and Tóth, 2016); an $O(\log^2 n)$-approximation in quasi-polynomial time $n^{O(\log\log n)}$ (Antoniadis, Kisfaludi-Bak, Laekhanukit and Vaz, 2022); APX-hardness, ruling out a PTAS unless $P=NP$ (same paper); and a PTAS when the neighborhoods are hyperplanes instead of lines in any fixed dimension (Antoniadis, Fleszar, Hoeksma and Schewior, 2020). The parallel-lines special case in 3-space reduces to the Euclidean TSP on points (intersect the lines with an orthogonal plane) and is NP-hard. These results are formulated in the real-RAM model, the standard model of computational geometry in which arithmetic on real coordinates is exact and unit-cost.

Within this landscape, the final remarks of Dumitrescu's 2012 paper pose two open problems: the exact complexity (polynomial-time solvability versus NP-hardness) of the optimal TSP tour or path for rays in the plane, and the existence of a good — in the field's established reading, constant-factor and polynomial-time — approximation for lines in 3-space.

Problem Statement

Resolve both of the following two questions, which are the open problems posed in the final remarks of Dumitrescu's 2012 paper on the TSP for lines and rays in the plane.

(I) Rays in the plane. Given a set of $n$ rays (half-lines) in the Euclidean plane, determine the exact computational complexity of computing a shortest tour (closed curve) visiting every ray, and of computing a shortest path visiting every ray: for each of the two variants separately, either exhibit a polynomial-time algorithm in the real-RAM model computing an optimal curve of that variant, or prove that the variant is NP-hard. The tour and the path variant are each required.

(II) Lines in 3-space. Given a set of $n$ lines in $\mathbb{R}^3$, settle whether a shortest tour visiting all lines, and a shortest path visiting all lines, can each be approximated within a constant factor in polynomial time: for each of the two variants separately, either exhibit a polynomial-time algorithm achieving an $O(1)$-approximation for that variant, or prove that the variant admits no polynomial-time constant-factor approximation, i.e. that for every constant $c>1$ there is no polynomial-time $c$-approximation for that variant (under explicitly stated standard complexity assumptions). The tour and the path variant are each required. A PTAS is impossible unless $P=NP$ by the known APX-hardness, and the parallel-lines special case already encodes the NP-hard Euclidean TSP on points, so the question is precisely whether the gap between the polylogarithmic upper bounds and APX-hardness can be closed at the constant-factor level.

Both components, and within each component both the tour and the path variant, are part of the objective.

References

1. Esther M. Arkin and Refael Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics 55:197–218, 1994. DOI: 10.1016/0166-218X(94)90008-6. https://doi.org/10.1016/0166-218X(94)90008-6
2. Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, and A. Frank van der Stappen. TSP with neighborhoods of varying size. Journal of Algorithms 57(1):22–36, 2005. DOI: 10.1016/j.jalgor.2005.01.010. https://doi.org/10.1016/j.jalgor.2005.01.010
3. Håkan Jonsson. The Traveling Salesman Problem for lines in the plane. Information Processing Letters 82(3):137–142, 2002. DOI: 10.1016/S0020-0190(01)00259-9. https://doi.org/10.1016/S0020-0190(01)00259-9
4. Adrian Dumitrescu. The Traveling Salesman Problem for Lines and Rays in the Plane. Discrete Mathematics, Algorithms and Applications 4(4):1250044, 2012. DOI: 10.1142/S1793830912500449. arXiv:1204.5828. https://doi.org/10.1142/S1793830912500449
5. Adrian Dumitrescu and Minghui Jiang. Minimum-Perimeter Intersecting Polygons. Algorithmica 63(3):602–615, 2012. DOI: 10.1007/s00453-011-9516-3. https://doi.org/10.1007/s00453-011-9516-3
6. Adrian Dumitrescu and Csaba D. Tóth. The Traveling Salesman Problem for Lines, Balls, and Planes. ACM Transactions on Algorithms 12(3), Article 43, 2016. DOI: 10.1145/2850418. arXiv:1303.6659. https://doi.org/10.1145/2850418
7. Xuehou Tan. The touring rays and related problems. Theoretical Computer Science 866:43–55, 2021. DOI: 10.1016/j.tcs.2021.03.005. (Conference version: Xuehou Tan. Polynomial-Time Algorithms for the Touring Rays and Related Problems. Algorithmic Aspects in Information and Management (AAIM 2020), Lecture Notes in Computer Science, pages 1–12. DOI: 10.1007/978-3-030-57602-8_1.) https://doi.org/10.1016/j.tcs.2021.03.005
8. Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, and Kevin Schewior. A PTAS for Euclidean TSP with Hyperplane Neighborhoods. ACM Transactions on Algorithms 16(3), Article 38, 2020. DOI: 10.1145/3383466. arXiv:1804.03953. https://doi.org/10.1145/3383466
9. Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. Computing Smallest Convex Intersecting Polygons. Journal of Computational Geometry 16(1):167–202, 2025. DOI: 10.20382/jocg.v16i1a6. arXiv:2208.07567. https://doi.org/10.20382/jocg.v16i1a6
10. Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), LIPIcs, pages 10:1–10:21, 2022. DOI: 10.4230/LIPIcs.SWAT.2022.10. arXiv:2008.12075. https://doi.org/10.4230/LIPIcs.SWAT.2022.10