Minimal link visibility paths inside a simple polygon (Q2367125)

The paper shows that the following problem is \(NP\)-hard: Given a simple polygon \(P\) in the plane find a polygonal path \(\pi\) with a minimum number of edges so that any point inside \(P\) is visible from some point on \(\pi\) (``minimal link visibility path''). In addition it is shown that it is \(NP\)-hard to find a minimum link tour inside a given polygon \(P\) visiting a given set \(S\) of points on the boundary of \(P\). The reduction is from the settheoretic Exact-three-cover (\(X3C\)) problem. The paper also presents a polynomial time algorithm for finding a visibility path whose link-length is at most three times as long as the optimal one.