2026-07-23T16:36:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13808 2024-03-06T10:52:46Z ddc:004 open_access

Rectilinear Steiner Trees in Narrow Strips Alkema, Henk de Berg, Mark Computational geometry fixed-parameter tractable algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henk Alkema and Mark de Berg 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.9 urn:nbn:de:0030-drops-138081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode