We address the 1-line minimum Steiner tree of line segments (1L-MStT-LS) problem. Specifically, given a set S of n disjoint line segments in $\mathbb{R}^2$, we are asked to find the location of a line l and a set El of necessary line segments (i.e., edges) such that a graph consisting of all line segments in S ∪ El plus this line l, denoted by Tl = (S, l, El), becomes a Steiner tree, the objective is to minimize total length of edges in El among all such Steiner trees. Similarly, we are asked to find a set E0 of necessary edges such that a graph consisting of all line segments in S ∪ E0, denoted by TS = (S, E0), becomes a Steiner tree, the objective is to minimize total length of edges in E0 among all such Steiner trees, we refer to this new problem as the minimum Steiner tree of line segments (MStT-LS) problem. In addition, when two endpoints of each edge in E0 need to be located on two different line segments in S, respectively, we refer to that problem as the minimum spanning tree of line segments (MST-LS) problem. We obtain three main results: (1) Using technique of Voronoi diagram of line segments, we design an exact algorithm in time O(nlogn) to solve the MST-LS problem; (2) we show that the algorithm designed in (1) is a 1.214-approximation algorithm to solve the MStT-LS problem; (3) using the combination of the algorithm designed in (1) as a subroutine for many times, a technique of finding linear facility location and a key lemma proved by techniques of computational geometry, we present a 1.214-approximation algorithm in time O(n3logn) to solve the 1L-MStT-LS problem.
[1] Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48-50(1956)
[2] Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2008)
[3] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
[4] Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047(2000)
[5] Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16-34(2002)
[6] Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM J. Comput. 5(4), 724-742(1976)
[7] Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Long Beach, Calif, pp. 151-162(1975)
[8] Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, New York (2008)
[9] Bose, P., Toussaint, G.: Growing a tree from its branches. J. Algorithms 19(1), 86-103(1995)
[10] Borgelt, M.G., van Kreveld, M., Löffler, M., Luo, J., Merrick, D., Silveira, R.I., Vahedi, M.: Planar bichromatic minimum spanning trees. J. Discrete Algorithms 7(4), 469-478(2009)
[11] Dey, S., Jallu, R.K., Nandy, S.C.: Minimum spanning tree of line segments. Lect. Not. Comput. Sci. 10976, 529-541(2018)
[12] Chen, G., Zhang, G.: A constrained minimum spanning tree problem. Comput. Oper. Res. 27(9), 867-875(2000)
[13] Aazami, A., Cheriyan, J., Jampani, K.R.: Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs. Algorithmica 63(1-2), 425-456(2012)
[14] Ljubić, I.: Solving Steiner trees: recent advances, challenges, and perspectives. Networks 77(2), 177- 204(2020)
[15] Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55-89(1992)
[16] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)
[17] Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122-134(2005)
[18] Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 1-33(2013)
[19] 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)
[20] Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782(1998)
[21] Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomialtime approximation scheme for geometric TSP, k-MStT, and related problems. SIAM J. Comput. 28, 1298-1309(1999)
[22] Rao, S.B., Smith, W.D.: Approximating geometrical graphs via “panners” and “banyans”. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, New York, pp. 540-550(1999)
[23] Cieslik, D.: Steiner Minimal Trees. Kluwer Academic Publishers, Dordrecht (1998)
[24] Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
[25] Holby, J.: Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad. Math. J. 18(1), 123-155(2017)
[26] Li, J., Liu, S., Lichen, J., Wang, W., Zheng, Y.: Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J. Comb. Optim. 39, 492-508(2020)
[27] Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1-29(1968)
[28] Chung, F., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. Ann. N. Y. Acad. Sci. 440(1), 328-346(1985)
[29] Megiddo, N., Tamir, A.: Finding least-distances lines. SIAM J. Algebraic Discrete Methods 4, 207-211(1981)
[30] Althaus, E., Rauterberg, F., Ziegler, S.: Computing Euclidean Steiner trees over segments. EURO J. Comput. Optim. 8, 309-325(2020)
[31] Juhl, D., Warme, D.M., Winter, P., Zachariasen, M.: The Geosteiner software package for computing Steiner trees in the plane: an updated computational study. Math. Program. Comput. 10, 487-532(2018)
