Abstract
In this paper, we study the parameterized complexity of some variants of the watchman route problem on line segment arrangements. We show that finding a minimum length Watchman Tree/Route on line Segment arrangements (WTS/WRS) is Fixed Parameter Tractable (FPT) with respect to the number of vertices in the tree/route as the parameter. We then prove that another variant of WTS referred to as Minimum Corridor Connection (MCC), is FPT with respect to the number of regions as the parameter. We also consider WRS with the link distance metric (LWRS) and propose an FPT algorithm for a restricted version in which each line segment in the input arrangement has a bound on the number of intersections it makes with other segments in the arrangement.
Disclosure statement
No potential conflict of interest was reported by the author(s).