Rectilinear Steiner Trees in Narrow Strips
Discrete & Computational Geometry · 2026-12 · 76 (4) · 2272-2300
DOI: 10.1007/s00454-026-00866-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete & Computational Geometry, online erschienen am 05.08.2026. Verfasst von Henk Alkema und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Nederlandse Organisatie voor Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
A rectilinear Steiner tree for a set P of points in $$\mathbb {R}^2$$ R 2 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 minimum total length. We investigate how the complexity of Minimum Rectilinear Steiner Tree for point sets P inside a $$\delta $$ δ -strip—that is, a strip of the form $$(-\infty ,+\infty )\times [0,\delta ]$$ ( - ∞ , + ∞ ) × [ 0 , δ ] —depends on the strip width $$\delta $$ δ . We obtain three main results. We present an algorithm that finds an optimal monotonic rectilinear Steiner tree in O ( n ) time, assuming the points are already sorted by x -coordinate. We show that when the difference between any two distinct x -coordinates is at least $$\delta $$ δ , then an optimal monotonic rectilinear Steiner tree for a point set inside a $$\delta $$ δ -strip is also optimal among all (possibly non-monotonic) rectilinear Steiner trees. Next, we consider sparse points sets, that is, point sets such that any $$1\times \delta $$ 1 × δ rectangle inside the $$\delta $$ δ -strip contains O (1) points. We first show that an optimal monotonic rectilinear Steiner tree provides an $$O(\delta )$$ O ( δ ) -approximation of an optimal rectilinear Steiner tree. Second, we present an algorithm with running time $$n^{O(\sqrt{\delta })}$$ n O ( δ ) that computes an optimal rectilinear Steiner tree for sparse point sets. For point sets whose points are chosen randomly inside the rectangle $$[0,n]\times [0,\delta ]$$ [ 0 , n ] × [ 0 , δ ] , we present an algorithm that is fixed-parameter tractable with respect to $$\delta $$ δ and linear in n . It has an expected running time of $$2^{O(\delta \sqrt{\delta })} n$$ 2 O ( δ δ ) n .
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, the Netherlands.
ORCID-Profile: Mark de Berg
Förderung
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Zitieren
APA
Alkema, H., & de Berg, M. (2026). Rectilinear Steiner Trees in Narrow Strips. Discrete & Computational Geometry, 76(4), 2272-2300. https://doi.org/10.1007/s00454-026-00866-2
Vancouver
Alkema H, de Berg M. Rectilinear Steiner Trees in Narrow Strips. Discrete & Computational Geometry. 2026;76(4):2272-2300. doi:10.1007/s00454-026-00866-2
BibTeX
@article{Alkema2026,
author = {Alkema, Henk and de Berg, Mark},
title = {Rectilinear Steiner Trees in Narrow Strips},
journal = {Discrete & Computational Geometry},
year = {2026},
volume = {76},
number = {4},
pages = {2272--2300},
doi = {10.1007/s00454-026-00866-2}
}
EUVIMED