Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem
Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang
2024, 12(3):
729-755.
doi:10.1007/s40305-022-00437-1
Asbtract
(
169 )
PDF
References |
Related Articles |
Metrics
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.
