Abstract
In this paper, we consider the 1-line minimum rectilinear Steiner tree (1L-MRST) problem, which is defined as follows. Given n points in the Euclidean plane \(\mathbb {R}^2\), we are asked to find the location of a line l and a Steiner tree T(l), which consists of vertical and horizontal line segments plus the line l, to interconnect these n points and at least one point on the line l, the objective is to minimize total weight of T(l), i.e., \(\min \{\sum _{uv\in T(l)} w(u,v)\) | T(l) is a Steiner tree as mentioned-above\(\}\), where weight \(w(u,v)=0\) if two endpoints u, v of an edge \(uv \in T(l)\) is located on the line l and weight w(u, v) as the rectilinear distance between u and v otherwise. Given a line l as an input, we refer to this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRST) problem; In addition, when Steiner points of T(l) are all located on the line l, we refer to this problem problem as the constrained minimum rectilinear Steiner tree (CMRST) problem.
We obtain three main results as follows. (1) We design an exact algorithm in time \(O(n\log n)\) to solve the CMRST problem; (2) We show that the same algorithm in (1) is a 1.5-approximation algorithm to solve the 1LF-MRST problem; (3) Using a combination of the algorithm in (1) for many times and a key lemma proved by using some techniques of computational geometry, we provide a 1.5-approximation algorithm in time \(O(n^3\log n)\) to solve the 1L-MRST problem.
This paper is supported by Project of the National Natural Science Foundation of China [Nos. 11861075, 11801498], Project for Innovation Team (Cultivation) of Yunnan Province, Joint Key Project of Yunnan Provincial Science and Technology Department and Yunnan University [No. 2018FY001014] and IRTSTYN. In addition, J.R. Lichen is also supported by Project of Doctorial Fellow Award of Yunnan Province [No. 2018010514].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berg, M.d., Cheong, O., Kreveld, Mv., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, New York (2008)
Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171–176 (1989)
Cheng, X.Z., Du, D.Z.: Steiner Trees in Industry. Combinatorial Optimization 11. Kluwer Academic Publishers, Dordrecht, The Netherlands (2001)
Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835–859 (1977)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
Holby, J.: Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad. Math. J. 18(1), 123–155 (2017)
Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30(1), 104–114 (1976)
Hwang, F.K.: An \(O(n\log n)\) algorithm for rectilinear minimal spanning trees. J. ACM 26(2), 177–182 (1979)
Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55–89 (1992)
Imase, M., Waxman, B.M.: Dynamic Steiner tree problem, Technical Report No. WUCS-89-11, Department of Computer Science, Washington University, St. Louis, MO (1989)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)
Morris, J.G., Norback, J.P: A simple approach to linear facility location. Transp. Sci. 14(1), 1–8 (1980)
Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
Riehards, D.: Fast heuristic algorithms for rectilinear Steiner trees. Algorithmica 4, 191–207 (1989)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science, pp. 151–162. IEEE Computer Society (1975)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-04565-7_30
Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)
Zhou, H., Shenoy, N., Nicholls, W.: Efficient minimum spanning tree construction without Delaunay triangulation. Inf. Process. Lett. 81, 271–276 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Lichen, J. et al. (2020). On Approximations for Constructing 1-Line Minimum Rectilinear Steiner Trees in the Euclidean Plane \(\mathbb {R}^2\). In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)