DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.6

Geometric TSP on Sets

Authors: Henk Alkema and Mark de Berg

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

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.

Cite as

Henk Alkema and Mark de Berg. Geometric TSP on Sets. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.ISAAC.2023.6,
  author =	{Alkema, Henk and de Berg, Mark},
  title =	{{Geometric TSP on Sets}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.6},
  URN =		{urn:nbn:de:0030-drops-193083},
  doi =		{10.4230/LIPIcs.ISAAC.2023.6},
  annote =	{Keywords: Euclidean TSP, TSP on Sets, Rectilinear TSP, TSP on Neighbourhoods}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.5

TSP in a Simple Polygon

Authors: Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

We study the Traveling Salesman Problem inside a simple polygon. In this problem, which we call tsp in a simple polygon, we wish to compute a shortest tour that visits a given set S of n sites inside a simple polygon P with m edges while staying inside the polygon. This natural problem has, to the best of our knowledge, not been studied so far from a theoretical perspective. It can be solved exactly in poly(n,m) + 2^O(√nlog n) time, using an algorithm by Marx, Pilipczuk, and Pilipczuk (FOCS 2018) for subset tsp as a subroutine. We present a much simpler algorithm that solves tsp in a simple polygon directly and that has the same running time.

Cite as

Henk Alkema, Mark de Berg, Morteza Monemizadeh, and Leonidas Theocharous. TSP in a Simple Polygon. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.ESA.2022.5,
  author =	{Alkema, Henk and de Berg, Mark and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{TSP in a Simple Polygon}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.5},
  URN =		{urn:nbn:de:0030-drops-169434},
  doi =		{10.4230/LIPIcs.ESA.2022.5},
  annote =	{Keywords: Traveling Salesman Problem, Subexponential algorithms, TSP with obstacles}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.9

Rectilinear Steiner Trees in Narrow Strips

Authors: Henk Alkema and Mark de Berg

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

A rectilinear Steiner tree for a set P of points in ℝ² is a tree that connects the points in P using horizontal and vertical line segments. The goal of {Minimum Rectilinear Steiner Tree} is to find a rectilinear Steiner tree with minimal total length. We investigate how the complexity of {Minimum Rectilinear Steiner Tree} for point sets P inside the strip (-∞,+∞)× [0,δ] depends on the strip width δ. We obtain two main results. - We present an algorithm with running time n^O(√δ) for sparse point sets, that is, point sets where each 1×δ rectangle inside the strip contains O(1) points. - For random point sets, where the points are chosen randomly inside a rectangle of height δ and expected width n, we present an algorithm that is fixed-parameter tractable with respect to δ and linear in n. It has an expected running time of 2^{O(δ √{δ})} n.

Cite as

Henk Alkema and Mark de Berg. Rectilinear Steiner Trees in Narrow Strips. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.SoCG.2021.9,
  author =	{Alkema, Henk and de Berg, Mark},
  title =	{{Rectilinear Steiner Trees in Narrow Strips}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.9},
  URN =		{urn:nbn:de:0030-drops-138081},
  doi =		{10.4230/LIPIcs.SoCG.2021.9},
  annote =	{Keywords: Computational geometry, fixed-parameter tractable algorithms}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2020.4

Euclidean TSP in Narrow Strips

Authors: Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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³).

Cite as

Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4,
  author =	{Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor},
  title =	{{Euclidean TSP in Narrow Strips}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.4},
  URN =		{urn:nbn:de:0030-drops-121628},
  doi =		{10.4230/LIPIcs.SoCG.2020.4},
  annote =	{Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms}
}

Search Results

Documents authored by Alkema, Henk

Geometric TSP on Sets

Abstract

Cite as

TSP in a Simple Polygon

Abstract

Cite as

Rectilinear Steiner Trees in Narrow Strips

Abstract

Cite as

Euclidean TSP in Narrow Strips

Abstract

Cite as

Thanks for your feedback!

Could not send message