EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Rectilinear Steiner Trees in Narrow Strips

Henk Alkema, Mark de Berg iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Approximation algorithmsComputational geometryFixed-parameter tractable algorithmsRectilinear Steiner trees

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}
}
Kostenlos starten →