2026-07-24T09:35:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19308 2024-03-06T11:03:43Z ddc:004 open_access

Geometric TSP on Sets Alkema, Henk de Berg, Mark Euclidean TSP TSP on Sets Rectilinear TSP TSP on Neighbourhoods In One-of-a-Set TSP, also known as the Generalised TSP, the input is a collection 𝒫 : = {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 ℝ^d that is contained in a given hypercube H_i. We investigate how the complexity of Euclidean One-of-a-Set TSP depends on λ, the ply of the set ℋ := {H_1, ..., H_r} of hypercubes (The ply is the smallest λ such that every point in ℝ^d is in at most λ of the hypercubes). Furthermore, 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. Finally, we show 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 ℋ of hypercubes in ℝ^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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henk Alkema and Mark de Berg 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.6 urn:nbn:de:0030-drops-193083 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.6 eng https://creativecommons.org/licenses/by/4.0/legalcode