In One-of-a-Set TSP , also known as the Generalised TSP , the input is a collection P : = { P 1 , . . . , P r } of sets in a metric space and the goal is to compute a minimum-length tour that visits one element from each set. In the Euclidean variant of this problem, each P i is a set of points in R d . Let H i be a hypercube that contains P i , for 1 ⩽ i ⩽ r . We investigate how the complexity of Euclidean One-of-a-Set TSP depends on λ , the ply of the set H : = { H 1 , . . . , H r } of hypercubes. (The ply is the smallest λ such that every point in R d is contained in at most λ of the hypercubes). We show that the problem can be solved in 2 O ( λ 1 / d n 1 − 1 / d ) time, where n : = ∑ i = 1 r | P i | is the total number of points, and that the problem cannot be solved in 2 o ( n ) time when λ = Θ ( n ) , unless the Exponential Time Hypothesis (ETH) fails. In Rectilinear One-of-a-Cube TSP , the input is a set H of hypercubes in R d and the goal is to compute a minimum-length rectilinear tour that visits every hypercube. We show that the problem can be solved in 2 O ( λ 1 / d n 1 − 1 / d log ⁡ n ) time, where n is the number of hypercubes.

We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results. - For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).