Title: A Linear-time Algorithm for Orthogonal Watchman Route Problem with Minimum Bends,
Abstract: Given an orthogonal polygon $ P $ with $ n $ vertices, the goal of the
watchman route problem is finding a path $ S $ of the minimum length in $ P $
such that every point of the polygon $ P $ is visible from at least one of the
point of $ S $. In the other words, in the watchman route problem we must
compute a shortest watchman route inside a simple polygon of $ n $ vertices
such that all the points interior to the polygon and on its boundary are
visible to at least one point on the route. If route and polygon be orthogonal,
it is called orthogonal watchman route problem. One of the targets of this
problem is finding the orthogonal path with the minimum number of bends as
possible. We present a linear-time algorithm for the orthogonal watchman route
problem, in which the given polygon is monotone. Our algorithm can be used also
for the problem on simple orthogonal polygons $ P $ for which the dual graph
induced by the vertical decomposition of $ P $ is a path, which is called path
polygon.