2026-07-24T05:42:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19327 2024-03-06T11:03:46Z ddc:004 open_access

Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets Dhar, Anubhav Hait, Soumita Kolay, Sudeshna Steiner minimal tree Euclidean Geometry Almost Convex point sets FPTAS strong NP-completeness The Euclidean Steiner Minimal Tree problem takes as input a set P of points in the Euclidean plane and finds the minimum length network interconnecting all the points of P. In this paper, in continuation to the works of [Du et al., 1987] and [Weng and Booth, 1995], we study Euclidean Steiner Minimal Tree when P is formed by the vertices of a pair of regular, concentric and parallel n-gons. We restrict our attention to the cases where the two polygons are not very close to each other. In such cases, we show that Euclidean Steiner Minimal Tree is polynomial-time solvable, and we describe an explicit structure of a Euclidean Steiner minimal tree for P. We also consider point sets P of size n where the number of input points not on the convex hull of P is f(n) ≤ n. We give an exact algorithm with running time 2^𝒪(f(n) log n) for such input point sets P. Note that when f(n) = 𝒪(n/(log n)), our algorithm runs in single-exponential time, and when f(n) = o(n) the running time is 2^o(n log n) which is better than the known algorithm in [Hwang et al., 1992]. We know that no FPTAS exists for Euclidean Steiner Minimal Tree unless P = NP [Garey et al., 1977]. On the other hand FPTASes exist for Euclidean Steiner Minimal Tree on convex point sets [Scott Provan, 1988]. In this paper, we show that if the number of input points in P not belonging to the convex hull of P is 𝒪(log n), then an FPTAS exists for Euclidean Steiner Minimal Tree. In contrast, we show that for any ε ∈ (0,1], when there are Ω(n^ε) points not belonging to the convex hull of the input set, then no FPTAS can exist for Euclidean Steiner Minimal Tree unless P = NP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anubhav Dhar and Soumita Hait and Sudeshna Kolay 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.25 urn:nbn:de:0030-drops-193273 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode