LIPIcs.SoCG.2021.9.pdf
- Filesize: 0.93 MB
- 16 pages
Document
Rectilinear Steiner Trees in Narrow Strips
Authors
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Acknowledgements
We thank Remco van der Hofstad for discussions about the probabilistic analysis.
Cite AsGet BibTex
Henk Alkema and Mark de Berg. Rectilinear Steiner Trees in Narrow Strips. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.9
https://doi.org/10.4230/LIPIcs.SoCG.2021.9
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Computational geometry
- fixed-parameter tractable algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in narrow strips. In Proc. 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of LIPIcs, pages 4:1-4:16, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.4.
-
E. Althaus. Berechnung optimaler Steinerbäume in der ebene. Master’s thesis, Max-Planck-Institutfür Informatik in Saarbrücken, Universität des Saarlandes, 1998.
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proc. 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pages 67-74. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250801.
- Marcus Brazil, Doreen A. Thomas, Jia F. Weng, and Martin Zachariasen. Canonical forms and algorithms for Steiner trees in uniform orientation metrics. Algorithmica, 44(4):281-300, 2006. URL: https://doi.org/10.1007/s00453-005-1178-6.
- Marcus Brazil and Martin Zachariasen. Steiner trees for fixed orientation metrics. J. Glob. Optim., 43(1):141-169, 2009. URL: https://doi.org/10.1007/s10898-008-9305-y.
- Marcus Brazil and Martin Zachariasen. The uniform orientation Steiner tree problem is NP-hard. Int. J. Comput. Geom. Appl., 24(2):87-106, 2014. URL: https://doi.org/10.1142/S0218195914500046.
- Marcus Brazil and Martin Zachariasen. Optimal Interconnection Trees in the Plane, volume 29. Springer, May 2015. URL: https://doi.org/10.1007/978-3-319-13915-9.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.
- D.J. Daley and D. Vere-Jones. An Introduction to the Theory of Point Processes: Volume II: General Theory and Structure. Probability and Its Applications. Springer New York, 2007. URL: https://books.google.nl/books?id=nPENXKw5kwcC.
- Linda Deneen, Gary Shute, and Clark Thomborson. A probably fast, provably optimal algorithm for rectilinear Steiner trees. Random Structures & Algorithms, 5:535-557, October 1994. URL: https://doi.org/10.1002/rsa.3240050405.
- S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: https://doi.org/10.1002/net.3230010302.
- Fedor Fomin, Daniel Lokshtanov, Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. Subexponential algorithms for rectilinear Steiner tree and arborescence problems. ACM Transactions on Algorithms, 16:1-37, March 2020. URL: https://doi.org/10.1145/3381420.
- M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics, 32(4):835-859, 1977. URL: http://www.jstor.org/stable/2100193.
- M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826-834, 1977. URL: http://www.jstor.org/stable/2100192.
- E. N. Gilbert and H. O. Pollak. Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1):1-29, 1968. URL: http://www.jstor.org/stable/2099400.
- M. Hanan. On Steiner’s problem with rectilinear distance. SIAM Journal on Applied Mathematics, 14(2):255-265, 1966. URL: http://www.jstor.org/stable/2946265.
- F. K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics, 30(1):104-114, 1976. URL: http://www.jstor.org/stable/2100587.
- Daniel Juhl, David Warme, Pawel Winter, and Martin Zachariasen. The geoSteiner software package for computing Steiner trees in the plane: an updated computational study. Mathematical Programming Computation, 10:487-532, 2018. URL: https://doi.org/10.1007/s12532-018-0135-8.
- Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. URL: https://doi.org/10.1007/s00453-012-9630-x.
- Clark D. Thomborson, Bowen Alpern, and Larry Carter. Rectilinear Steiner tree minimization on a workstation. In Proce. DIMACS Workshop on Computational Support for Discrete Mathematics, volume 15 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 119-136, 1992. URL: https://doi.org/10.1090/dimacs/015/10.
- Clark D. Thomborson, Linda L. Deneen, and Gary M. Shute. Computing a rectilinear Steiner minimal tree in n^O(√n) time. In Proc. International Workshop on Parallel Algorithms and Architectures, volume 269 of Lecture Notes in Computer Science, pages 176-183, 1987. URL: https://doi.org/10.1007/3-540-18099-0_44.
-
David Warme. Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, University of Virginia, 1998.
- Peter Widmayer, Ying-Fung Wu, and C. K. Wong. On some distance problems in fixed orientations. SIAM J. Comput., 16(4):728-746, 1987. URL: https://doi.org/10.1137/0216049.
- Pawel Winter. An algorithm for the steiner problem in the euclidean plane. Networks, 15(3):323-345, 1985. URL: https://doi.org/10.1002/net.3230150305.