Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R d (d-RSP), for a given set S of n points in R d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time O ⁎ ( ( 1 + 1 + 4 ( d − 1 ) 2 ) k ) is given for the Constrained d-RSP problem, which significantly improves the current best result O ⁎ ( ( 0. 74 d k ) k ).

Authors

• Qilong Feng
• Jianxin Wang
• Chao Xu Zhejiang University
• Jinyi Yao
• Jianer Chen

Keywords

• Rectilinear spanning path
• Parameterized algorithm
• Line cover
• Axis-parallel line