Rectilinear steiner trees in narrow strips

Henk Y. Alkema; Mark de Berg

doi:10.4230/LIPIcs.SoCG.2021.9

Rectilinear steiner trees in narrow strips

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

A rectilinear Steiner tree for a set P of points in R² 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.

Original language	English
Title of host publication	37th International Symposium on Computational Geometry, SoCG 2021
Editors	Kevin Buchin, Eric Colin de Verdiere
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	9783959771849
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2021.9
Publication status	Published - 1 Jun 2021
Event	37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States Duration: 7 Jun 2021 → 11 Jun 2021

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	189
ISSN (Print)	1868-8969

Conference

Conference	37th International Symposium on Computational Geometry, SoCG 2021
Country/Territory	United States
City	Virtual, Buffalo
Period	7/06/21 → 11/06/21

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).

Funding

Funding The work in this paper is supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

Keywords

Computational geometry
Fixed-parameter tractable algorithms

Access to Document

10.4230/LIPIcs.SoCG.2021.9

Cite this

@inproceedings{e86580ef27f84cf586f446b7abc96212,

title = "Rectilinear steiner trees in narrow strips",

abstract = "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.",

keywords = "Computational geometry, Fixed-parameter tractable algorithms",

author = "Alkema, {Henk Y.} and {de Berg}, Mark",

note = "Publisher Copyright: {\textcopyright} Henk Alkema and Mark de Berg; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).; 37th International Symposium on Computational Geometry, SoCG 2021 ; Conference date: 07-06-2021 Through 11-06-2021",

year = "2021",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2021.9",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Kevin Buchin and {de Verdiere}, {Eric Colin}",

booktitle = "37th International Symposium on Computational Geometry, SoCG 2021",

}

Alkema, HY & de Berg, M 2021, Rectilinear steiner trees in narrow strips. in K Buchin & EC de Verdiere (eds), 37th International Symposium on Computational Geometry, SoCG 2021., 9, Leibniz International Proceedings in Informatics, LIPIcs, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37th International Symposium on Computational Geometry, SoCG 2021, Virtual, Buffalo, United States, 7/06/21. https://doi.org/10.4230/LIPIcs.SoCG.2021.9

Rectilinear steiner trees in narrow strips. / Alkema, Henk Y.; de Berg, Mark.
37th International Symposium on Computational Geometry, SoCG 2021. ed. / Kevin Buchin; Eric Colin de Verdiere. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 189).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Rectilinear steiner trees in narrow strips

AU - Alkema, Henk Y.

AU - de Berg, Mark

N1 - 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).

PY - 2021/6/1

Y1 - 2021/6/1

N2 - 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.

AB - 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.

KW - Computational geometry

KW - Fixed-parameter tractable algorithms

UR - http://www.scopus.com/inward/record.url?scp=85108220964&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2021.9

DO - 10.4230/LIPIcs.SoCG.2021.9

M3 - Conference contribution

AN - SCOPUS:85108220964

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Computational Geometry, SoCG 2021

A2 - Buchin, Kevin

A2 - de Verdiere, Eric Colin

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 37th International Symposium on Computational Geometry, SoCG 2021

Y2 - 7 June 2021 through 11 June 2021

ER -

Rectilinear steiner trees in narrow strips

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this