Rectilinear steiner trees in narrow strips

Henk Y. Alkema, Mark de Berg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


A rectilinear Steiner tree for a set P of points in R2 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 nO(√δ) 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 2O(δ√δ)n.

Original languageEnglish
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771849
Publication statusPublished - 1 Jun 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: 7 Jun 202111 Jun 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo

Bibliographical note

Publisher Copyright:
© Henk Alkema and Mark de Berg; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).


  • Computational geometry
  • Fixed-parameter tractable algorithms


Dive into the research topics of 'Rectilinear steiner trees in narrow strips'. Together they form a unique fingerprint.

Cite this