Polygon exploration with time-discrete vision (Q1037781)

A comprehensive study of the online watchman problem with discrete vision is presented exploring all of an unknown region in the presence of a fixed cost for each scan. The authors focus on the case of rectilinear polynoms. It is demonstrated that a competitive strategy is possible only if maximum and minimum edge length in the polygons are bounded. For the case of rectilinear polygons, a matching competitive strategy with performance \({\mathcal O}(\log A) \) is provided, where \(A\) is the aspect ratio of maximum and minimum edge length.