Geometric TSP on sets

In ONE-OF-A-SET TSP, also known as the GENERALISED TSP, the input is a collection P:={P₁,...,Pr} 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 Pi is a set of points in Rd. Let Hi be a hypercube that contains Pi, 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₁,...,Hr} of hypercubes. (The ply is the smallest λ such that every point in Rd is contained in at most λ of the hypercubes). We show that the problem can be solved in 2O(λ1/dn1−1/d) time, where n:=∑i=1r|Pi| is the total number of points, and that the problem cannot be solved in 2o(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 Rd and the goal is to compute a minimum-length rectilinear tour that visits every hypercube. We show that the problem can be solved in 2O(λ1/dn1−1/dlog⁡n) time, where n is the number of hypercubes.