On the Minimum Link-Length Rectilinear Spanning Path Problem: Complexity and Algorithms

摘要

The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the -dimensional Euclidean space (-RSP), for a given set of points in and a positive integer , is to find a piecewise-linear path with at most line-segments that covers (i.e., contains) all points in , where all line-segments in 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 -RSP problem in which each line-segment in the spanning path must cover all the points in the given set that share the same line with . We present a new parameterized algorithm with running time for the constrained -RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time for the constrained -RSP problem for a fixed . We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.