On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms Academic Article uri icon

abstract

  • 2013 IEEE. The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space d (d-RSP), for a given set S of n points in d and a positive integer k, is to find a piecewise-linear path P with at most k line-segments that covers (i.e., contains) all points in S, where all line-segments in P are axis-parallel. We first prove that the problem 2-RSP is NP-complete, improving the previously known result that the problem 10-RSP is NP-complete. We then consider a constrained d-RSP problem in which each line-segment s in the spanning path must cover all the points in the given set S that share the same line with s. We present a new parameterized algorithm with running time O((2d)k) for the constrained d-RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time O(2O(k)) for the constrained d-RSP problem for a fixed d. We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.

published proceedings

  • IEEE Transactions on Computers

author list (cited authors)

  • Wang, J., Tan, P., Yao, J., Feng, Q., & Chen, J.

citation count

  • 7

complete list of authors

  • Wang, Jianxin||Tan, Peiqiang||Yao, Jinyi||Feng, Qilong||Chen, Jianer

publication date

  • December 2014