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 Jian-Ping Li;Su-Ding Liu;Jun-Ran Lichen;Peng-Xiang Pan;Wen-Cheng Wang

作者机构：Department of MathematicsYunnan UniversityKunming650504YunnanChina School of Mathematics and PhysicsBeijing University of Chemical TechnologyBeijing650504China 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2024年第12卷第3期

页      面：729-755页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported by the National Natural Science Foundation of China(Nos.11861075 and 12101593) Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE160006) Key Project of Yunnan Provincial Science and Technology Department and Yunnan University(No.2018FY001014) Program for Innovative Research Team(in Science and Technology)in Universities of Yunnan Province(No.C176240111009) Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.Su-Ding Liu is also supported by the Graduate Research and Innovation Project of Yunnan University(No.2020Z66) 

主　　题：1-Line minimum Steiner tree of line segments Minimum spanning tree of line segments Voronoi diagram of line segments Steiner ratio Approximation algorithms 

摘      要：We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)***,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner ***,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)*** addition,when two endpoints of each edge in Eo 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)*** obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)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(n^(3) log n)to solve the 1L-MStT-LS problem.