5 Search Results for "Alkema, Henk"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.46
Realizing Metric Spaces with Convex Obstacles

Authors: Sándor Kisfaludi-Bak and Leonidas Theocharous

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The presence of obstacles has a significant impact on distance computation, motion-planning, and visibility. These problems have been studied extensively in the planar setting, while our understanding of these problems in 3- and higher-dimensional spaces is still rudimentary. In this paper, we study the impact of different types of obstacles on the induced geodesic metric in 3-dimensional Euclidean space. We say that a finite metric space (X, dist_X) is approximately realizable by a collection 𝒯 of obstacles in ℝ³ if for any ε > 0 it can be embedded into (ℝ³⧵⋃_{T∈𝒯} T, dist_𝒯) with worst-case multiplicative distortion 1+ε, where dist_𝒯 denotes the geodesic distance in the free space induced by 𝒯. We focus on three key geometric properties of obstacles -convexity, disjointness, and fatness- and examine how dropping each one of them affects the existence of such embeddings. Our main result concerns dropping the fatness property: we demonstrate that any finite metric space is realizable with 1+ε worst-case multiplicative distortion using a collection of convex and pairwise disjoint obstacles in ℝ³, even if the obstacles are congruent and equilateral triangles. Based on the same construction, we can also show that if we require fatness but drop any of the other two properties instead, then we can still approximately realize any finite metric space. Our results have important implications on the approximability of tsp with obstacles, a natural variant of tsp introduced recently by Alkema et al. (ESA 2022). Specifically, we use the recent results of Banerjee et al. on tsp in doubling spaces (FOCS 2024) and of Chew et al. on distances among obstacles (Inf. Process. Lett. 2002) to show that tsp with obstacles admits a PTAS if the obstacles are convex, fat, and pairwise disjoint. If any of these three properties is dropped, then our results, combined with the APX-hardness of Metric tsp, demonstrate that tsp with obstacles is APX-hard.
Cite as

Sándor Kisfaludi-Bak and Leonidas Theocharous. Realizing Metric Spaces with Convex Obstacles. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2025.46,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Theocharous, Leonidas},
  title =	{{Realizing Metric Spaces with Convex Obstacles}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{46:1--46:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.46},
  URN =		{urn:nbn:de:0030-drops-249545},
  doi =		{10.4230/LIPIcs.ISAAC.2025.46},
  annote =	{Keywords: traveling salesman, geodesic distance}
}
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}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2022
  • 1 2021
  • 1 2020

  • Refine by Author
  • 4 Alkema, Henk
  • 4 de Berg, Mark
  • 2 Kisfaludi-Bak, Sándor
  • 2 Theocharous, Leonidas
  • 1 Monemizadeh, Morteza

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Computational geometry

  • Refine by Keyword
  • 2 Computational geometry
  • 2 Euclidean TSP
  • 2 fixed-parameter tractable algorithms
  • 1 Rectilinear TSP
  • 1 Subexponential algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact